故同余方程x2≡42(mod 107)有解。
3、求（127156+34）28除以111的最小非负余数。 解：易知1271≡50（mod 111）。
由502 ≡58（mod 111）, 503 ≡58×50≡14（mod 111），509≡143≡80（mod 111）知5028 ≡（509）3×50≡803×50≡803×50≡68×50≡70（mod 111） 从而5056 ≡16（mod 111）。
故（127156+34）28≡（16+34）28 ≡5028≡70（mod 111） 三、证明题
1、已知p是质数，（a,p）=1，证明：
（1）当a为奇数时，ap-1+(p-1)≡0 (mod p)； （2）当a为偶数时，ap-1-(p-1)≡0 (mod p)。
证明：由欧拉定理知ap-1≡1 (mod p)及(p-1)≡-1 (mod p)立得（1）和（2）成立。
2、设a为正奇数，n为正整数，试证a2na
aa
≡1(mod 2n+2)。 …………… （1）
证明 设a = 2m ? 1，当n = 1时，有
a2 = (2m ? 1)2 = 4m(m ? 1) ? 1 ? 1 (mod 23)，即原式成立。 设原式对于n = k成立，则有
2其中q?Z，所以 ak?1a2k? 1 (mod 2k + 2) ?a2= 1 ? q2k + 2，
k= (1 ? q2k + 2)2 = 1 ? q ?2k + 3 ? 1 (mod 2k + 3)，
其中q ?是某个整数。这说明式(1)当n = k ? 1也成立。 由归纳法知原式对所有正整数n成立。
k
3、设p是一个素数，且1?k?p-1。证明：Ckp?1 ? （-1 ）(mod p)。
（p?1）(p?2)?(p?k) 证明：设A=Ckp?1? 得：
k! k!·A =（p-1）(p-2)…（p-k）≡（-1）(-2)…（-k）(mod p)
k
又（k!，p）=1，故A = Ckp?1 ? （-1 ）(mod p)
4、设p是不等于3和7的奇质数，证明：p6≡1(mod 84)。 说明：因为84=4×3×7，所以，只需证明：
p6≡1(mod 4) p6≡1(mod3) p6≡1(mod 7) 同时成立即可。 证明：因为84=4×3×7及p是不等于3和7的奇质数，所以
（p，4）=1，（p，3）=1，（p，7）=1。
由欧拉定理知：p?(4)≡p2≡1(mod 4)，从而 p6≡1(mod 4)。
同理可证：p6≡1(mod3) p6≡1(mod 7)。 故有p6≡1(mod 84)。
注：设p是不等于3和7的奇质数，证明：p6≡1(mod 168)。（见赵继源p86）
初等数论练习题二
一、填空题
1、d(1000)=_16_；σ(1000)=_2340_. 2、2010!的标准分解式中，质数11的次数是199__. 3、费尔马(Fermat)数是指Fn=22+1,这种数中最小的合数Fn中的n=5。 4、同余方程13x≡5(mod 31)的解是x≡29(mod 31)___ 5、分母不大于m的既约真分数的个数为?(2)+ ?(3)+…+ ?(m)。 6、设7∣(80n-1),则最小的正整数n=_6__. 7、使41x+15y=C无非负整数解的最大正整数C=__559__. 8、??46??=_1__. 101??n9、若p是质数，n?p ? 1，则同余方程x n ? 1 (mod p) 的解数为n . 二、计算题
20031、试求20022004被19除所得