47197是合數(改錯重貼）

解：

令p=47197。

判斷 2^47196 被 p除，是否余1。

試解得2^73 (mod p)=2

將47916分解如下：

47196 = 73(73)(8)+73(62)+38          (1)

2^47196 = 2^(73(73)(8)) 2^(73(62)) 2^38

2^47196 (mod p)= 2^(73(73)(8)) 2^(73(62)) 2^38 (mod p)

= 2^8 2^62 2^38 (mod p)=2^108 (mod p)=2^73 2^35 (mod p)

=2^36 (mod p)=2^27 2^9 (mod p)= 36657(512) (mod p)=31175

因 2^47196 (mod 47197) != 1, 47197是合數。