フェルマーの小定理の問題－解答編－

フェルマーの小定理について

フェルマーの小定理については、既に説明しました。

ｐを素数とするとき、ａとｐが互いに素ならば、ａ^(p-1)－１≡０(mod p）です。

フェルマーの小定理及び整数の問題の解答

【問題１】２^100を９７で割った余りを暗算で求めてください。
答え：１６です。自明です。
問題2】ａ^2－ａが１００００で割り切れる自然数ａで最小のものを求めてください。（東大　改）
解答

\(ａ^2－ａ\)＝ａ（ａ－１）となり、１００００＝\(２^4・５^4\)　ですから、　　　ａ（ａ－１）＝\(２^4・５^4\)　･･･････①　となります。

ここで、ａが奇数のときは、ａ－１は偶数ですから、

ａ＝\(5^4\)・ｎ･･･････②

ｂ＝\(２^4\)・ｍ･･････③　とかけます。ｎは正の奇数、ｍは自然数です。　　①、②、③から、

６２５ｎ＝１６ｍ＋１となります。よって、

ｍ＝（６２５ｎ－１）/１６＝（ｎ－１）/１６＋３９ｎ　となります。ｍは自然数ですから、ｎ＝１６ｋ＋１（ｋは整数）　従って、

ａ＝６２５(１６ｋ＋１）＝１００００ｋ＋６２５　となります。

よって、奇数ａの最小値は、ｋ＝０の時、６２５となります。

（東大の問題は、ａが奇数であると言う条件がついているので、６２５が答えとなります。）

ａが偶数の時は、ａ－１が奇数となります。従って、ａが奇数の時と同様にして、

ａ－１＝\(５^4\)・ｐ　（ｐは正の奇数）

ａ＝\(２^4\)・ｑ　（ｑは自然数）

よって、これから、上と同様にして、

ｑ＝（６２５ｐ＋１）/１６＝（ｐ＋１）/１６＋３９ｐ

ここで、ｑは、自然数ですから、ｐ＋１＝１６ｋ（ｋ＝1,2,3････）

従って、ａ＝６２５（１６ｋ－１）＋１＝１００００ｋ－６２５＋１

＝１００００ｋ－６２４　となります。

これを満たす偶数ａは、ｋ＝１の時で、ａ＝９３７６

以上から、最小の自然数ａは、６２５です。･････（答）