同余方程求解

aimisiyou

`\begin{equation}\begin{cases}
ax-bc\equiv 0\mod{(a^2-b^2)},\\
bx-ac\equiv 0\mod{(a^2-b^2)}
\end{cases}\end{equation}`
`a,b,c` 均为自然数且`a>b`,求满足条件的最小的正整数`x`？

hujunhua

当`\gcd(a,b)=1`时，两式可以互相导出，即只有一个独立同余方程。
两边相加后除以`(a+b)`得`x\equiv c\mod(a-b)`
两式相减后除以`(a-b)`得`x\equiv -c\mod(a+b)`
然后用中国剩余定理。要分`\gcd(a+b,a-b)=1,2`两种情况。

mathe

对于一般情况${(x-=c (\mod a-b)),(x-=-c(\moda+b)):}$也成立，
这是因为两式相加得出$a^2-b^2|(a+b)(x-c)$,所以必然$a-b|x-c$,另外一个关系也同样得出。
于是设$d=gcd(a-b,a+b)$,于是方程有解的一个必要条件是$c-=x-=-c(\mod d)$
所以得出$d|2c$,或者说$gcd(a-b,a+b)|2c$

mathe

类似可以证明$gcd(a-b,a+b)|c$是有解的充分条件

aimisiyou

mathe 发表于 2016-6-18 18:41
类似可以证明$gcd(a-b,a+b)|c$是有解的充分条件

若a,b互质，是否一定有解？

mathe

是的

mathe

gcd(a,b)|c即可证明有解

aimisiyou

\(\begin{pmatrix}n_1\\n_2\end{pmatrix}=\begin{pmatrix}a&b\\b&a\end{pmatrix}^{-1}\begin{pmatrix}c\\x\end{pmatrix}\), 若 \(x=x_0\) 满足\(\begin{pmatrix}n_1\\n_2\end{pmatrix}\)为正整数时，则\(x=x_0+K(a^2-b^2)\)

aimisiyou

再进一步，\(\begin{pmatrix}n_1\\n_2\\n_3\end{pmatrix}=\begin{pmatrix}a&b&c\\c&a&b\\b&c&a\end{pmatrix}^{-1}\begin{pmatrix}d\\x\\y\end{pmatrix}\)有正整数解的充分条件和必要条件分别是什么？（d>a>b>c均为已知正整数,x,y未知）