Question

初等数论同余问题的题目

说明 2^(2^5)+1 是否能被641整除

求（257^33 +46 ）^26 被50除的余数

求 n=7^(7^7) 的个位数

Answer 1

（1）说明 2^(2^5)+1 是否能被641整除
解：2^(2^5)+1 能被641整除
即2^32+1==0mod641,参见
http://hi.baidu.com/wsktuuytyh/blog/item/ea41b7638df4cd6c0d33fa42.html

只须证2^(2^5)==2^32==-1 mod 641.

(以下记ax==b mod m为x==b/a mod m,这是洪伯阳记法，很好用)
2^6=64==-1/10 mod 641,故2^7==-1/5,(2^7)^4==1/625==-1/16,从而2^32==-1.毕。

写成一般的形式：
2^6=64mod 641,故5*2^7==640==-1,1==(5*2^7)^4==(625)*2^28==-16*2^28=-2^32,从而2^32==-1.毕。

（2）求（257^33 +46 ）^26 被50除的余数
解：
φ(50)=20.故所求==(7^13-4)^6==(7*49^6-4)^6==3^6=729==29

（3）求 n=7^(7^7) 的个位数
解：φ(10)=4.
7^7 mod 4==(-1)^7==-1==3
n mod 10==7^3 mod 10==3

Answer 2

2^(2^5)+1 是能被641整除

（257^33 +46 ）^26 被50除的余数29

Answer 3

能
29
3