《初等数论》习题解答(第三版)广东石油化工学院
243x??30?112?mod551? 2?5??同?i?的方法的得其解是x?200?mod551?
?原同余式的解是x?200,751,1302,1853,2404?mod2755?
?iii?(1296,1935)=9,故原同余式有9个解。
由144x??30?125?mod215?得x?80?mod215? 2?5???原同余式的解是x?80?215t?mod1935?,t?0,18.
2.求联立同余式??x?4y?29?0(mod143)的解。
2x?9y?84?0(mod143)?解:据同余式的有关性质,
?x?4y?29?0(mod143)?x?4y?29(mod143) ????2x?9y?84?0(mod143)?17y??1(mod143)?x?4y?29(mod143)?x?4(mod143)为所求的解。 ????y?42(mod143)y?42(mod143)??3.(i)设m是正整数,(a,m)?1.证明
?(m?)1(modm ) x?ba是同余式 ax?b(modm)的解 (ii)设p是质数,0?a?p,证明
x?b(?1)a?1(p?1)(p?a?1)(modp)
a!是同余式ax?b(modp)的解. 证明: (i)
(a,m)?1 , ?ax?b(modm) 有唯一解.
而据欧拉定理,得 a?(m)?1(modm),
31 / 77
《初等数论》习题解答(第三版)广东石油化工学院
ax?b(momd)?a?(m?)1?ax?ba?m(?)1(momd)
即 x?ba?(m)?1(modm)是ax?b(modm)的解. (ii) 又
0?a?p?(a,p)?1 即ax?b(modp)有唯一解
a个连续整数之积必被a!所整除,
(p?1)(p?a?1)故可令 ab(?1)a?1?k
a!则b(?1)a?1(p?1)(p?a?1)?k(a?1)!
(p?a?1)?b(?1)2(a?1)(a?1)!(modp)
b(?1)a?1(p?1)即b(?1)2(a?1)(a?1)!?k(a?1)!(modp)
?k?b(modp)
即 x?b(?1)a?1(p?1)(p?a?1)(modp)
a!是ax?b(modp)的解.
设p是素数,0 < a < p,证明:
x?b(?1)a?1(p?1)(p?2)???(p?a?1)(mod p)。
a!是同余方程ax ? b (mod p)的解。
(p?1)(p?2)???(p?a?1)是整数,又由(a, p) = 1知方程ax ?
a!(p?1)(p?2)???(p?a?1)b (mod p)解唯一,故只须将x?b(?1)a?1(mod p)代入ax ? b
a!解:首先易知b(?1)a?1(mod p)验证它是同余方程的解即可。
4.设m是正整数,?是实数,1???m,(a,m)?1,证明同余式
ax?y(modm),0?x??,0?y?有解.
m?
32 / 77
《初等数论》习题解答(第三版)广东石油化工学院
证明: 因(a,m)?1. 故同余式 ax?1(modm) 必有解x0, (i) (ii)