一、填空题
初等数论练习题一
1、d2420122420_880_
2、设a
是大于1的整数，若a
1是质数，则a_23、模9的绝对最小完全剩余系是_4，3，2，1012344、同余方程9x12≡0mod37的解是x≡11mod37。5、不定方程18x23y100的通解是x90023t，y70018ttZ。6、分母是正整数m的既约真分数的个数为_m_。7、18100被172除的余数是_256。
8、651。
103
9、若p是素数，则同余方程xp11modp的解数为p1。二、计算题1、解同余方程：3x211x200mod105。
解：因105357，同余方程3x211x200mod3的解为x1mod3，同余方程3x211x380mod5的解为x0，3mod5，同余方程3x211x200mod7的解为x2，6mod7，故原同余方程有4解。作同余方程组：xb1mod3，xb2mod5，xb3mod7，
其中b11，b20，3，b32，6，由孙子定理得原同余方程的解为x13，55，58，100mod105。2、判断同余方程x2≡42mod107是否有解？
解：42（237）（2）（3）（7）
107
107
107107107
（2）1，（3）（1）3211072（1107）（2）1，（7）（1）7211072（1107）（2）1
107
107
3
3
107
7
7
（42）1107
故同余方程x2≡42mod107有解。
3、求（12715634）28除以111的最小非负余数。
f解：易知1271≡50（mod111）。由502≡58（mod111）503≡58×50≡14（mod111），509≡143≡80（mod111）知5028≡（509）3×50≡803×50≡803×50≡68×50≡70（mod111）从而5056≡16（mod111）。故（12715634）28≡（1634）28≡5028≡70（mod111）
三、证明题1、已知p是质数，（ap）1，证明：
（1）当a为奇数时，ap1p1a≡0modp；
（2）当a为偶数时，ap1p1a≡0modp。
证明：由欧拉定理知ap1≡1modp及p1a≡1modp立得（1）和（2）成立。
2、设a为正奇数，
为正整数，试证a2
≡1mod2
2。……………（1）
证明设a2m1，当
1时，有
a22m124mm111mod23，即原式成立。
设原式对于
k成立，则有a2k1mod2k2a2k1q2k2，
其中qZ，所以a2k11q2k221q2k31mod2k3，
其中q是某个整数。这说明式1当
k1也成立。
由归纳法知原式对所有正整数
成立。
3、设
p
是一个素数，且
1≤k≤p1。证明：
Ckp1

（1
）kmod
p。
证明：设
A
Ckp1
（p

1）p
2k
p

k

得：
kA（p1）p2…（pk）≡（1）2…（k）modp
又（k，p）1，故A

Ckp1

（1
）kmod
p
4、设p是不等于3和7的奇质数，证明：p6≡1mod84。
说明：因为844×3×7，所以，只需证明：
p6≡1mod4
p6≡1mod3
p6≡1mod7同时成立即可。
证明：因r