一次同余式通解

fungarwai

能不能化简或推广？

fungarwai

原理是辗转相除法
12x+1≡0(mod 31)
→5x'+1≡0(mod 7)
→x''+1≡0(mod 2)
→x'''+1≡0(mod 1)
n=(cn'+bk)/c'
x'''=0（任取）→x''=1→x'=4→x=18
现在用公式从最后任取0一下子推到x=18

fungarwai

嗯，看了。
那个方法不错，但我想把它弄成通解。
不然每次都这样代来代去很慢......

fungarwai

math_humanbeing 发表于 2013-12-17 21:30
不是有扩展欧几里德算法吗？

看到它的矩阵法了。感谢告知，的确比较简单。

fungarwai

2x+3y+5z=1
(x,y,z)=(2+3a+5b,-1-2a+5c,-2b-3c)
如果写成(-2+3a'+5b',-2a'+5c',1-2b'-3c')
考虑a'=a+3,b'=b-1,c'=c+1
跟(2+3a+5b,-1-2a+5c,-2b-3c)一样

解ax+by+cz=d时
任设x0,y0,z0使ax0+by0+cz0=d

这个矩阵可以推广到n元

=========================================
有点错，修正：

kastin

当且仅当`(a,m)|b`时，一次同余方程`ax \equiv b \pmod{m}`有解。
考虑`(a,m)=1`的情形。因为若`(a,m)=d`，`a,b,m`可以同时除以`d`，总可得到$$ax \equiv b \pmod{m} \quad (a,m)=1\tag{1}$$的形式。

因为`(a,m)=1`，故必有整数`s,t`满足`as+mt=1`，于是$$as \equiv 1 \pmod{m}\tag{2}$$而`(m,b)=1`,根据同余式乘法性质，有$$abs \equiv b \pmod{m}$$即$$x \equiv bs \pmod{m}$$为方程`(1)`的解。
根据欧拉定理，若`(a,m)=1`，则`a^{\varphi(m)} \equiv 1 \pmod{m}`，于是$$s \equiv a^{\varphi(m)-1} \pmod{m}$$是方程`(2)`的解。
所以方程`(1)`的最终解可写为$$x \equiv a^{\varphi(m)-1}b \pmod{m}\tag{3}$$由于欧拉函数`\varphi(x)`定义为不超过`x`的正整数数中与`x`互质的个数。显然当`m`或`a`很大时，如果用手工计算，`(3)`就显得非常麻烦。