Question

一次同余式方程怎么解？ 127*x=833(mod 1012)

一次同余式方程怎么解？
127*x=833(mod 1012)
有些数字很变态怎么办？
我想直接用计算机编程算了……
有没会什么方法计算时会方便点呀？

Answer 1

解：∵(127,1012)=1 ((a,b)表示a和b的最大公因数)
且(127,1012)│833 (a│b表示b被a整除)
∴127x≡833 (mod 1012) 有解，且只有1个解。
∵7*127x≡7*833≡771 (mod 1012)
==>(1012-123)x≡771 (mod 1012)
==>-123x≡771 (mod 1012)
==>123x≡-771≡241 (mod 1012)
==>8*123x≡241*8≡-96 (mod 1012)
==>(1012-28)x≡-96 (mod 1012)
==>-28x≡-96 (mod 1012)
==>28x≡96 (mod 1012)
又(28,1012)=4，且4│96
∴28x≡96 (mod 1012)与7x≡24 (mod 253)的解是一致。对于模1012只有4

个解，对于模253有1个解。
∵36*7x≡24*36≡105 (mod 253)
==>(253-1)x≡105≡-148 (mod 253)
==>-x≡-148 (mod 253)
==>x≡148 (mod 253)
∴28x≡96 (mod 1012)的4个解是 x≡148，401，654，907 (mod 1012)
经验算，x≡907 (mod 1012)是127x≡833 (mod 1012) 的解。
故同余式127x≡833 (mod 1012) 的解是x≡907 (mod 1012)。

Answer 2

127*x=833(mod 1012)

为方便打字，改写成 127x==833 mod 1012
写成不定方程，得
127x = 833 + 1012y
将127的倍数集中到127x这一项上面并引入新变量，可写为
127z = -56 - 4y
将4的倍数集到中4y这一项上，立即知道 可取 z=0, y=-14，然后回代，马上得到x.
另外，我们也可以用下面的技巧，简化计算过程来求得x.
将上面两个式子比较可得到
x-z=7+8y, 故x=z+7+8y=7-8*14=-105 mod 1012==907

Answer 3

1012 = 4*11*23，
两边模 4 得 -x≡1，因此 x≡-1≡3(mod 4)，
两边模 11 得 6x≡8，因此 3x≡4，12x≡x≡16(mod 11)，
两边模 23 得 12x≡5，因此 24x≡x≡10(mod 23)，
由剩余定理知，原不定方程的解是
x≡3*(11*23)+16*(4*23*3)+10*(4*11*11)≡10015≡907 (mod 1012) 。

Answer 4

x==833/127==(833ⅹ8)/4==[(833x8x32-833)/(4x32-127)]mod1012==212415mod1012
==907mod1012
注:这是我二十多年用笔大量海算找到的一次不定方程(一次同余式)的本质系统理论解法…如想了解请看我这两年在微博上所解的题!

Answer 5

∵(127,1012)=1 ((a,b)表示a和b的最大公因数)
且(127,1012)│833 (a│b表示b被a整除)
∴127x≡833 (mod 1012) 有解,且只有1个解.
∵7*127x≡7*833≡771 (mod 1012)
==>(1012-123)x≡771 (mod 1012)
==>-123x≡771 (mod 1012)
==>123x≡-771≡241 (mod 1012)
==>8*123x≡241*8≡-96 (mod 1012)
==>(1012-28)x≡-96 (mod 1012)
==>-28x≡-96 (mod 1012)
==>28x≡96 (mod 1012)
又(28,1012)=4,且4│96
∴28x≡96 (mod 1012)与7x≡24 (mod 253)的解是一致.对于模1012只有4
个解,对于模253有1个解.
∵36*7x≡24*36≡105 (mod 253)
==>(253-1)x≡105≡-148 (mod 253)
==>-x≡-148 (mod 253)
==>x≡148 (mod 253)
∴28x≡96 (mod 1012)的4个解是 x≡148,401,654,907 (mod 1012)
经验算,x≡907 (mod 1012)是127x≡833 (mod 1012) 的解.
故同余式127x≡833 (mod 1012) 的解是x≡907 (mod 1012).