关于初等数论的8道题目~谢谢250分1.求证：若a^k≡1(modm),a^n≡1(modm),且(k,n)=d,则a^d≡1(modm).2.设s(a)表示不大于a且与a互质的全体正整数的和,求证：s(a)=(1/2)a×φ(a)3.设m>0,(a,m)=1,b是正整数,证明：

Question

关于初等数论的8道题目~谢谢250分
1.求证：若a^k≡1(mod m),a^n ≡1(mod m),且(k,n)=d,则a^d ≡ 1(mod m).
2.设s(a)表示不大于a且与a互质的全体正整数的和,求证：s(a)=(1/2)a×φ(a)
3.设m>0,(a,m)=1,b是正整数,证明：若x取遍模m的完全剩余系,则Σ{(ax+b)/m}=(1/2)(m-1).
4.设m>0,(a,m)=1,证明：(上:m-1;下:x=1)Σ[ax/m]=(1/2)(m-1)(a-1).
5.证明：若p是大于2的质数,则(((p-1)/2)!)^2+(-1)^((p-1)/2) ≡0(mod p)
6.证明：若p为质数,则(p-1)!≡p-1 (mod p(p-1))
7.求所有的正整数对(x,y),满足x^y = y^(x-y)；
8.求方程(5^x)-(3^y)=2的所有正整数解.
（第三题和第四题似乎有联系哦）
...这次上课,Fermat小定理的题目就是没有听懂……什么是剩余类,完系,缩系,都似懂非懂的.
过一会儿我会提高悬赏分，我从来不会缺分的！

Answer 1

1.因为(k,n)=d,则存在整数s,t,使得ks+nt=d.
所以a^(ks)=1(mod m)
a^(nt)=1(mod m)
a^d=a^(ks+nt)=1(mod m)
2.因为当(b,a)=1当且仅当(a-b,a)=1.
用如同高斯求1+2+.+100相同的方法可知：
和=1/2 *(a-b+b) *φ(a)=1/2 *a*φ(a).
3.需要证ax+b(x取遍m的完全剩余系)是m的完全剩余系.
因为ax+b=ay+b(mod m)
当且仅当a(x-y)=0(mod m)
当且仅当m|a(x-y).
因为(a,m)=1.
所以m|x-y.
即x=y(mod m).
所以所求式子=1/m+2/m+.+(m-1)/m=1/2 *(m-1).
4.接上题：
所求式子=a/m+2a/m+.+(m-1)a/m-1/2 *(m-1).
=1/2 *(m-1)(a-1).
5.先看第6题,证明(p-1)!=-1(mod p).
因为p-a=-a(mod p).
所以(p-1)!=(((p-1)/2)!)*(-(p-1)/2)*.*(-2)(-1)
=(((p-1)/2)!)^2 * (-1)^((p-1)/2).
=-1(mod p).
所以(((p-1)/2)!)^2+(-1)^((p-1)/2)=0(mod p).
6.(p,p-1)=1.
(p-1)!=0(mod p-1).
下面证(p-1)!=-1(mod p).
p=2,3时成立；p>=5时：
首先对于任意a(2正无穷).
所以k=3,4时对应两组x=9,y=3; x=8,y=2.
且k>4时无解.
下面证21时：
原式mod 4：
1-(-1)^y=2(mod 4).
y=1(mod 2).
原式mod 9：
5^x=2(mod 9).
x=5(mod 6).
原式mod 7：
因为当x=5(mod 6)时,5^x=3(mod 7).
所以3^y=1(mod 7).
所以y=0(mod 6).
与y是奇数矛盾.
综上只有一组解x=y=1.