求解一次同余式

求解一次同余式

题：求解同余式35x==1 mod 97，问怎么用最大公因数的性质求解。
注意： mod 的本质是 0类剩余类。即　a mod m= a + 0 mod m=a + [0] = a+ m**，　[0]表示m的余数为0的剩余类，简称0类剩余类，**表示任意可变的整数值。]

题目转化：求解不定方程35x=1+97y
解一：
35x=1+97y
35z=1-8y 注：将35的倍数集中到35x上并改用新变量
3z=1-8w注：将8的倍数集中到8y上并改用新变量
由此立即看出可取特解z=3,w=-1,逆即得特解。
下面提出一种利于快速计算（特别是手算、口算心算）的细节算法将上面三个式子中的两邻的进行比较得
x-z=3y
4z=-y+w
故y=-4z+w=-13,x=z+3y=-36
即原同余式的解为x==-36==61 mod 97

验算：开始菜单-运行-calc(即打开windows计算器)-alt_CS(查看-科学型)，将
(35*(-36) % 97)
复制到其中，得到结果是 -96==1 mod 97.

解二：
引理：
存在x,y使得 ax+by=gcd(a,b)， 这里a,b,x,y全为整数。
注：gcd表示最大公约数great common divisor. 我们一般用辗转相除法求得最大公因数。
35与97的最大公因数为 1，下面用辗转相除法。

97=-8+35a, a=3;
35=3+8b, b=4;
8=-1+3c, c=3
由后两式消去除数3，得 8=-1+(35-8b)c，
归并除数8相关的项，得8(1+bc)=-1+35c
再与第一式联立消去除数8相关的项，得(35a-97)(1+bc)=-1+35c
于是35(a+abc-c)-97(1+bc)=-1
与35x==1 mod 97比较，知解
x==-(a+abc-c)=-36 mod 97
此即所求。

解三：（广义）连分数法。这个方法与解二原理相当，利用连分数的性质，过程很简洁。
97=35*3-8
35=4*8+3
8=3*3-1
故
97/35=3-1/(4+1/(3-1/3))=[3; -1:4; 1:3; -1:3]
[3; -1:4; 1:3]=3-1/(4+1/3)=3-3/13=36/13
故97*13-35*36=1
即35x==1 mod 97的解为
x==-36 mod 97

注：我定义广义连分数：
[Z；A1:B1,A2:B2,...]= Z+A1/(B1+A2/(B2+A3/(B3+...))),其中Z,Ai,Bi为整数，可以为负整数。

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息！