首先是裴蜀定理
对任意两个整数、，设是它们的最大公约数。那么关于未知数和的线性丢番图方程（称为裴蜀等式）： 有整数解(x,y) 当且仅当m 是d 的倍数。裴蜀等式有解时必然有无穷多个解。
对任意两个整数、，设是它们的最大公约数。那么关于未知数和的线性丢番图方程（称为裴蜀等式）：
有整数解(x,y) 当且仅当m 是d 的倍数。裴蜀等式有解时必然有无穷多个解。
扩展欧几里得算法
原文：http://www.cnblogs.com/sorhri/p/4833592.html
、
，设
是它们的最大公约数。那么关于未知数
和
的线性丢番图方程（称为裴蜀等式）：
