Question

说明2^2^5+1（即2^32+1）是否能被641整除.（用同余方法做）

Answer 1

题：求证641 | (2^32+1)

转化为求证 2^32 ==-1 mod 641,这里以==表示同余号.

下面的运算基于模(除数) 641.

易见 640=2^7 * 5== -1

故(2^7 * 5)^4 ==1

即 2^28* 625==1==2^28 * (-16)=-2^32

于是 2^32==-1

也可以用洪伯阳同余式记号来描述：

2^6=64==-1/10 mod 641

故 2^7==-1/5

2^28==1/625==-1/16

故2^32==-1