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<=a<=p-2)，存在唯一的b(2<=b<=p-2)，使得ab=1(mod p).
对于a、2a、......、(p-1)a这p-1个数中，它们两两mod p不同余。
否则存在i、j（i、j不相等）使得ia=ja(mod p).
p|a(i-j).
p|i-j.
则i=j，矛盾。
又因为ia mod p不为0，
所以a、2a、......、(p-1)a这p-1个数中，mod p是1~p-1的一个排列，
所以存在唯一的b(1<=b<=p-1)，使得ab=1(mod p).
又因为a与(p-1)a mod p都不为1，所以2<=b<=p-2.
这样，将每个a、b进行配对a1、b1、a2、b2......
2*3*......*(p-2)=(a1*b1)(a2*b2)......=1(mod p).
所以(p-1)!=1*1*(p-1)=-1(mod p).
综上(p-1)!=p-1(mod p(p-1)).

7. x^y=y^(x-y).
显然x-y>=0.
若x=y，则x^x=x^0=1. 则x=1, y=1.
若x>y，则y<x-y, x>2y.
设x=ky，k>2.
则k^y * y^y=y^((k-1)y).
ky=y^(k-1).
k=y^(k-2).
y=k^(1/(k-2)).
根据求导发现函数f(k)=k^(1/(k-2))在k>2递减，
而f(k)->正无穷(k->2), f(3)=3, f(4)=2, f(k)->1(k->正无穷).
所以k=3, 4时对应两组解：x=9, y=3; x=8, y=2.
且k>4时无解。
下面证2<k<3时无解即可。
因为k=x/y是有理数，设k=p/q, (p, q)=1.
所以y^(k-2)=k
y^(p/q -2)=p/q.
y^(p-2q)=(p/q)^q.
当q不为1时，左边是整数，右边不是整数，矛盾。
综上：x=1, y=1; x=8, y=2; x=9, y=3.

8. 5^x-3^y=2.
x=y=1是一组解.
当x>1, y>1时：
原式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.

Answer 2

问题太多，而且都比较难，给出2道的答案
1
设k = ds,n=dt
那么(s,t)=1
a^(ds) = 1 (mod m)
a^(dt) = 1 (mod m)
那么(a^d)^s = (a^d)^t = 1 (mod m)
设 u = a^d
所以u^s = 1,u^t = 1 (mod m)
由于(s,t) = 1 =>u^(s % t) = 1 .......
由辗转相除法可以得到u = 1 (mod m)
所以a^d = 1 (mod m)

7. x^y = y^(x-y)
x^y*y^y=y^x
xy = y^(x/y)
x = yu
y^2u = y^u
u = y^(u-2)
y = u^(1/(u-2))为整数，显然u必须为整数，所以u-2 = 1或u-2=-1 =>u=1或3
x = u^((u-1)/(u-2))
u = 1 =>x=y=1
u = 3 =>x=3,y=9
所以正整数解为(1,1)(3,9)