フェルマーの小定理の逆，ｑと互いに素な何れかのａについて，

　　ａ^q-1≠１　（ｍｏｄｑ）ならばｑは合成数

は成り立つだろうか？

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

　高次ベキ乗合同計算には工夫が必要である．ａ^c　（ｍｏｄｑ）を計算するのに際し，ｃを２進展開し

　　ｃ＝ｃ0＋ｃ1２＋ｃ2２^2＋・・・＋ｃk２^k

その後，ａj＝ａ^2^jを漸化式ｘａj+1＝（ａj）^2を用いて求め，

　　ａ^c＝Πａj　（ｍｏｄｑ）

の計算に進む．

［Ｑ］５２９３は合成数か？

［Ａ］５２９３＝６７・７９であるが，この素因数分解を知らないものとして

　　５２９２＝２^2＋２^3＋２^5＋２^7＋２^10＋２^12

２^2＝４，２^2^2＝１６，２^2^2^3＝１６^2＝２５６，

２^2^2^4＝２５６^2＝２０２０，

２^2^2^5＝２０２０^2＝４７９０，

２^2^2^6＝４７９０^2＝４２３８，

２^2^2^7＝４２３８^2＝１４９５，

２^2^2^8＝１４９５^2＝１３７９，

２^2^2^9＝１３７９^2＝１４５４，

２^2^2^10＝１４５４^2＝２２０９，

２^2^2^11＝２２０９^2＝４８２８，

２^2^2^12＝４８２８^2＝４５０５　　（ｍｏｄ５２９３）

以上より

２^5292＝１６・２５６・４７９０・１４９５・２２０９・４５０５＝２８９０　　（ｍｏｄ５２９３）

よって，５２９３は合成数．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝