解同余式2015-11-20
目录
解同余式 (1)
线性组合 (3)
几何解释 (3)
什么时候有解 (4)
最好的解 (5)
其他解 (5)
线性组合
22和18的最大公因子是2，可以找到他们的线性组合：
怎么样利用上面的5×18 – 4×22 = 2求下面的问题呢?
只需要进行一些变换：
最后得到：
176×22 –215×18 = 2
也就是说：
通过s×18 – t×22 = 2有办法得到s’×22 – t’×18 = 2
几何解释
两个数可以线性表达出它们的公因数：
如果把它们找一个周长18的桶卷起来，正好卷完第一个的时候第二个剩余2(公因数)：
再卷一次：
一直这样下去，9次(18÷2)之后就开始重复了。

什么时候有解
有解吗?
前面讨论中知道：
22x在向18的圆上卷的时候，一共有9种可能。

都在公因子2的刻度上：
5不在这个刻度上，所以没有解。

那该如何解，刻度上的：
前面已经知道
所以有：
最好的解
前面已经找到了一个解：
也就是：
1232×22 – T×18 = 14
做一个简单变换：
(1223 + 9)×22 – T×18 = 14
这样就得到了：
1223×22 + (11 – T)×18 = 14
再重复上面的工作：
(1214 + 9)×22 + (11 – T)×18 = 14 直到不能分离出9来：
8×22 + T’×18 = 14
这样就得到了：
8比前面的解1232看起来好很多。

其他解
前面知道好的解：
也就是：
8×22 – T×18 = 14
做一个简单变换：
(8 + 9 – 9)×22 - T×18 = 14
17×22 – (T+11)×18 = 14
再做一次又可以得到另一个解：(17 + 9 – 9 )×22 – T’×18 = 14
重复这个步奏就可以得到所有的解：
如果感兴趣可以加群：495438656。