不定方程、同余方程
（矩阵扩欧）
一、二元一次不定方程
定理1．二元一次不定方程ax+by=c
（1）若其中(a,b)∤c则原方程无整数解；
（2）若（a，b）=1，则原方程有整数解；
（3）若（a，b）｜c，则可以在方程两边同时除以（a，b），从而使原方程的一次项系数互质，从而转化为（2）的情形．
定理2．若不定方程ax+by=1有整数解$$x_0,y_0$$，则方程ax+by=c有整数解$$cx_0+bk,cy_0-ak ,(k \in Z)$$
a、b不互质，先同时除以gcd(a,b)
例1．求方程4x+5y=21的整数解．
解：因为方程4x+5y=1有一组解-1，1，
1、直观法（简单的方程）
凑出解
2、分离系数法（中等难度方程）
x=(1-5y)/4 为整数，所以y可以为1
3、扩欧法 （难的方程）
利用扩欧矩阵http://139.196.53.116/ml/index.php/archives/236/
所以方程4x+5y=21有一组解-21，21．
又因为方程4x+5y=0的所有整数解为5k, -4k (k为整数),
所以方程4x+5y=21的所有整数解为-21+5k,21-4k (k为整数)
取k=4化简得-1+5k, 5-4k.
定理3.ax+by=c的特解为$$x_0,y_0$$,则通解为$$x_0+\frac{b}{(a,b)}k,y_0-\frac{a}{(a,b)}k ,(k \in Z)$$
在解同余方程时用到
二、三元一次方程组
解法：消元变为二元一次方程
x+y+z=10 (1)
x+2y+3z=21 (2)
消元x得到 y + 2z = 11
解得y=1+2k,z=5-k代入(1)
得x=4-k三、三元一次方程
解法：设置中间变量t, 拆分两个二元一次方程，再消去t
12x+8y+36z=100
化简 3x+2y+9z=25
拆分3x+2y = t (1)
t + 9z = 25 (2)
解（1）得 x = t+2m ,y = -t-3m
解（2）得 t = 7+9n ,z = 2-n
消去t得 x=7+9n+2m, y=-7-9n-3m ,z=2-n直接扩欧
$$\begin{pmatrix} 1&0&0&12 \\0&1&0&8 \\0&0&1&36 \end{pmatrix}=\begin{pmatrix} 25&-25&0&100 \\2m&-3m&0&0 \\9n&-9n&-n&0 \end{pmatrix}$$
x=9n+2m+25,y=-9n-3m-25,z=-n
四、高次，分式不定方程
方法：因式分解，参数分离，Δ法，奇数偶数分析法，利用特殊模，不等式分析法、利用韦达定理、换元法
五、勾股数方程$$x^2+y^2=z^2 ,\ (x \perp y)$$
定理1：(证明方法类似令x=3k+1)
1、x、y有不同得奇偶性
2、x、y中有且只有一个被3整除
3、x、y、z中有且只有一个被5整除
举例：3,4,5;8,15,17;5,12,13;7,24,25
引理：$$xy=z^2$$ ， （x、y互质的正整数）的一切整数解可以写成
$$x=a^2,y=b^2,z=ab,a>0,b>0,(a,b)=1$$的形式
定理2：勾股方程中的偶数，假设为x，则
$$x=2ab,y=a^2-b^2,z=a^2+b^2,a>0,b>0,(a,b)=1 $$且a、b有不同奇偶性
推论：单位元上的有理数点可以表示为：
$$(\pm \frac{2ab}{a^2+b^2},\pm \frac{a^2-b^2}{a^2+b^2})$$或$$(\pm \frac{a^2-b^2}{a^2+b^2},\pm \frac{2ab}{a^2+b^2})$$
六、费马大定理
$$x^n+y^n=z^n,(n>2,n\in Z)$$没有非零整数解
推论 $$x^4+y^4=z^2$$没有非零整数解
七、同余方程
1、定理1：等价同余式 f(x)≡0 (mod m) ---(1)
1)设b(x)是整系数多项式，则同余方程(1)与
f(x) + b(x) ≡ b(x) (mod m)等价；
2)设b是整数，(b, m) = 1，则同余方程(1)与
bf(x) ≡ 0 (mod m)等价；
3)设m是素数，f(x) = g(x)h(x) ,g(x)与h(x)都是整系数多项式，又设$$x_0$$是同余方程(1)的解，
则$$x_0$$必是同余方程 g(x) ≡ 0 (mod m) 或 h(x) ≡ 0 (mod m)的解。
2、定理2：一次同余式基本解法
设a,b是整数，a ∤ m。则同余方程 ax ≡ b (mod m) ---(2)
1)有解的充要条件是(a, m) | b
2)若有解，则恰有d = (a, m)个解。
3)特别地，若(a, m)=1,则方程（2）有唯一解。
4)同余方程(2)等价于不定方程 ax+my=b
5)同余方程(2)的解为$$x$$ ≡ $$x_0+\frac{m}{d} r(mod\ m) , 0\leq r\leq d-1$$
例子
9x ≡ 12 (mod 15)
解：d=(9,15)=3 ,且3|12
故同余式有3个解
9x+15y=12有特解$$x_0=3$$
所以同余式解为：
x≡3+rm/d=3+5r(mod 15),r=0,1,2
即x≡3、8、13 (mod 15)
3、定理3：减小模--其他解法
设(a,m)=1,a<m,又设存在$$y \in Z$$使得a|b+ym，即满足my≡-b(mod a)
则x≡$$\frac{b+ym}{a}(mod \ m)$$是方程ax ≡ y(mod m)的解
本质类似辗转相除法（扩欧）
若(a,m)=d,先同时除d,再利用定理2求出全部解。
例子
解同余方程 325x ≡ 20 (mod 161)
解 d=1,原同余方程即是 3x ≡ 20 (mod 161)。
161y ≡ 20 (mod 3)
2y ≡ 1 (mod 3)
y ≡ 2 (mod 3)
x ≡ (20+2*161)/3 =114 (mod 161)
例子
9x ≡ 12 (mod 15)
先解 3x ≡ 4 (mod 5) 得$$x_0$$=3
又d=3,m/d=5取r=0，1，2代入$$x=x_0+rd$$
得x≡3、8、13 (mod 15)
4、定理4：减小系数--其他解法
设a > 0，且(a, m) = 1，$$a_1$$是m对模a的最小非负剩余，
则同余方程$$a_1x$$ ≡ $$-b\[\frac{m}{a}\](mod\ m)$$ 等价与同余方程 ax ≡ b (mod m)
例子
6x ≡ 7 (mod 23)
解5x ≡ -7*3 ≡ 2 (mod 23)
3x ≡-2*4 ≡8 (mod 23)
2x ≡ 8×7 ≡ 10 (mod 23)
x ≡ 5 (mod 23)
5、定理5：应用欧拉定理--其他解法
设(a, m) = 1，并且有整数$$\sigma$$ > 0使得 a $$^{\sigma}$$≡ 1 (mod m)
则同余方程ax ≡ b (mod m)的解是 x ≡ ba $$^{\sigma -1}$$ 1 (mod m).
例子
17x ≡ 14 (mod 21)
解 x ≡ ba $$^{\sigma -1}$$ 1 (mod m) = $$14\times 17^{11}$$≡ 7(mod 21)
八、简单同余方程组
1、同模同余方程组
3x+5y≡1(mod 7)
2x-3y≡2(mod 7)
(1)x2-(2)x3得
19y≡-4(mod 7)
5y≡-4(mod 7)
y≡2(mod 7) 代入（1）得x≡4(mod 7)
2、同余同余方程组
x ≡ 1(mod 14)
x ≡ 1(mod 10)
得 x≡1(mod [10,14])
x ≡ 13(mod 14)
x ≡ 9(mod 10)
得 x≡-1(mod [10,14])
九、孙子定理（互质同余方程组）
http://139.196.53.116/ml/index.php/archives/167/
罗博深：
三三数之剩二（除以3余2），五五数之剩三（除以5余3），七七数之剩二（除以7余2）
x=35a+57b+73c - lcm(3,5,7)
其中a mod 7 = 2,b mod 3=2,c mod 5=3
十、孙子定理（不互质同余方程组）
解法思路，合并2个同余方程组变为一个，不断重复这个过程，直到只剩下一个方程。
合并解方程可以用扩展欧几里得法
x≡$$a_1 (mod \ m_1)$$
x≡$$a_2 (mod \ m_2)$$
(得到
$$x = m_1x_1+a_1$$
$$x = m_2x_2+a_2$$
相减得$$ m_1x_1 = (a_2-a_1)+m_2x_2$$)
第一步、所以$$ m_1x_1 $$≡$$ (a_2-a_1) (mod\ m_2)$$
第二步、扩欧法解得$$ x_1 $$≡ X (mod $$\frac{m_2}{d}$$) ,$$d=(m_1,m_2)$$
第三步、二式等价于x≡$$(m_1X+a_1)(mod\ [m1,m2])$$
例子
存在一个数x，除以6余4，除以8余2，除以9余7，然后求这个数
演示合并前两个方程：
1、6x≡(2-4)(mod 8)
2、X≡1(mod 4)
3、合并后 x≡(6*1+4)(mod 24) ≡10 (mod 24)
（此例错误的）
小学奥数解法
以上各种一次不定方程（组）均可利用统一的方法做
存在一个数x，除以6余4，除以8余2，除以9余7，然后求这个数
1、x+6y=4 , x+8z=2.（题意）
消去x的 6y-8z=2 ，利用矩阵扩欧，解得 y=4m-1,z=3m-1
代入任意一式得x+24m=10
2、联立x+9n=7（题意） 消去x 得24m-9n=3，利用矩阵扩欧，解得 n=8t-3,m=3t-1
代入任意一式得 x=-72t+34