题目

再求几道”初等数论”的详解.
1.求13^2006的个位码.
2.设素数P≥5,证明P^2Ξ1（ mod24）
3.证明：若P为素数,证明：（P－1）!ΞP-1（mod p（p-1））

提问时间：2021-04-01

答案

既然是定向求助,还是答一下：
1、由3^4个位是1,指数可砍掉4的倍数,余下3^2个位是9
2、大于3的素数必是奇数,也不是3倍数.奇数的平方除以8余数是1；不是3倍数的数的平方除以3余数是1,所以原数除以（3*8＝）24余数＝1
3、p=2,3时显然成立,
p>＝5时,两边约去(p-1),只需要证明(p-2)!Ξ1 (mod p)
从2~p-2这p-3个数可以这样组对：每个元素与它的逆组对,则刚好不多不少组成(p-3)/2对,每对相乘除以p余数显然是1.（这里你只需要证明当ab＝1modp 与cd=1modp,a,b,c,d都不是1,或者-1时,a,b,c,d互不相同）
(p-2)!=2*3*.*(p-2)＝上述(p-3)/2对之积,除以p同余1
即(p-2)!＝1 mod p
证毕