数理論 へ戻る２ と ５ 以外の素数 ｎ について、 10n-1−１ は ｎ で割り切れる。
全体集合を自然数とします。
（１） 余りある数の合成
x で割りきれる数 と x で割ると ａ 余る数 をたす。出来あがった数を x で割った余りは、
ａ を x で割ったときの余りに等しい。
なぜなら、
ｐ x ＋（ ｑ x ＋ ａ ） ＝ x （ ｐ ＋ ｑ ）＋ ａ
x で割ると ａ 余る数 と x で割ると ｂ 余る数 をたす。出来あがった数を x で割った余りは、
ａ＋ｂ を x で割ったときの余りに等しい。
なぜなら、
（ ｐ x ＋ ａ ）＋（ ｑ x ＋ ｂ ） ＝ x （ ｐ ＋ ｑ ） ＋ （ ａ ＋ ｂ ）
x で割ると ａ 余る数 と x で割ると ｂ 余る数 をかける。出来あがった数を x で割った余りは、
ａｂ を x で割ったときの余りに等しい。
なぜなら、
（ ｐ x ＋ ａ ） （ ｑ x ＋ ｂ ） ＝ ｐｑ x ２ ＋ x （ ｂｐ ＋ ａｑ ）＋ ａｂ
ｃ と ｍ が互いに素のとき、 ａｃ から ｂｃ を引いた数が ｍ で割り切れるならば、
ａ から ｂ を引いた数は ｍ で割り切れる。
（ 証 明 ）
ａｃ − ｂｃ ＝ ｍｋ
よって、 ｃ （ ａ−ｂ ） ＝ ｍｋ
ｃ と ｍ が互いに素なので、
ｋ ＝ ｃ かつ ａ−ｂ ＝ ｍ
したがって、 ａ−ｂ は ｍ で割り切れる。
（２） フェルマーの小定理
プログラムの内容 ：
フェルマーの小定理理を確かめる十進BASIC のプログラムを次に示します。
このフェルマーの小定理を証明しましょう。
ab−1 を b で割った余りが 1 である ならば ab を b で割った余りは a を b で割った余りに等しい。また、この逆の命題も真である。したがって、「 b は a の約数でない素数である ならば ab を b で割った余りは a を b で割った余りに等しい 」という命題が真であることを明らかにすることによってフェルマーの小定理の証明にかえさせてもらう。
a＝1 のとき、1b を b で割った余りは 1 であリ、1 を b で割った余りに等しい。
a＝k のとき、kb を b で割った余りは、k を b で割った余りに等しいと仮定する。
a＝k＋1 のとき、(k＋1)b ＝ kb ＋ bＣ1kb−1 ＋ bＣ2kb−2 ＋ ・・・ ＋ bＣb−1k ＋ 1
bＣd ( 1 ≦ d ≦ b−1 ) は b の倍数なの（※）で、(k＋1)b を b で割った余りは kb＋1 になる。仮定（ kb を b で割った余りは k である ）より、(k＋1)b を b で割った余りは k＋1 になる。
a＝1 のとき「 b は a の約数でない素数である ならば ab を b で割った余りは a を b で割った余りに等しい 」という命題は真であった。よって、a＝2 のときもこの命題は真である。ということは、a＝3 のときもこの命題は真である。ということは、・・・・。以上の数学的帰納法によって、この命題が真であることが明らかになった。
（※）の証明：
d × bＣd ＝→ d×b! / {d!×(b−d)!} ＝→ d×b×(b−1)! / {d×(d−1)!×(b−d)!}
＝→ b × (b−1)! / [(d−1)!×{(b−1)−(d−1)}!] ＝→ b × (b−1)Ｃ(d−1)
よって、 (b−1)Ｃ(d−1) ＝ d × bＣd / b
b が素数で 1 ≦ d ≦ b−1 のとき、b と d は互いに素であり、(b−1)Ｃ(d−1) は自然数だから、bＣd は b の倍数である。
素数 b が a の約数である場合はどうだろうか？ たとえば、 33−1 ＝→ 9 確かに 3 で割った余りは 1 になっていない。 23−1 ＝→ 4 や 43−1 ＝→ 16 とは違う。なぜだろう？ 今日はここまで。
参考： 論理学 ＞ フェルマーの小定理につながる背理法による証明
ａ から ｂ を引いた数は ｍ で割り切れる。
（ 証 明 ）
ａｃ − ｂｃ ＝ ｍｋ
よって、 ｃ （ ａ−ｂ ） ＝ ｍｋ
ｃ と ｍ が互いに素なので、
ｋ ＝ ｃ かつ ａ−ｂ ＝ ｍ
したがって、 ａ−ｂ は ｍ で割り切れる。
（２） フェルマーの小定理
-
全て公比５ の等差数列です。
１ ６ 11 16 21 26 ・ ・ ・ ・
２ ７ 12 17 22 27 ・ ・ ・ ・
３ ８ 13 18 23 28 ・ ・ ・ ・
４ ９ 14 19 24 29 ・ ・ ・ ・
５ 10 15 20 25 30 ・ ・ ・ ・
公差５ の等差数列をなす数は、 どれも ５ で割った余りが等しくなっています。 一番上の数列に注目してください。 これらの数から任意の２つを選んで掛け合わせた数を x とします。 また、 これらの数から新たに任意の２つを選んで掛け合わせた数を y とします。 すると、 x と y を ５ で割った余りは等しくなります。 たとえば次のようにです。
６ × 16＝ 96
11 × 26 ＝ 286
今度は、 ２つの公差５ の等差数列をなす数同士を掛け合わせてみましょう。 たとえば、
６ × 12 ＝ 72
11 × ２ ＝ 22
この場合も、 ５ で割った余りが必ず等しくなります。
したがって、
１ × ２ × ３ × ４ と 21 × ７ × 28 × 14 は ５ で割った余りが等しいです。
21 × ７ × 28 × 14 ＝ ７４×（ １ × ２ × ３ × ４ ） ですから、
１×24 と ７４×24 は ５ で割った余りが等しいです。
したがって、
７４×24 から １×24 を引いた数は ５ で割り切れます。
したがって、
７４ から １ を引いた数は ５ で割り切れます。
したがって、
７４ を ５ で割った余りは １ になります。
今回は、 ２つの素数 ５ と ７ を例にとって説明しましたが、 これを一般化しますと、 次のようになります。
素数 ｂ と ｂ の倍数でない整数 ａ があるとき、 ａｂ−１ を ｂ で割った余りは １ である。
次のプログラムはフェルマーの小定理が成り立つことを実感するためのものです。
プログラムの内容 ：
フェルマーの小定理理を確かめる十進BASIC のプログラムを次に示します。
このフェルマーの小定理を証明しましょう。
ab−1 を b で割った余りが 1 である ならば ab を b で割った余りは a を b で割った余りに等しい。また、この逆の命題も真である。したがって、「 b は a の約数でない素数である ならば ab を b で割った余りは a を b で割った余りに等しい 」という命題が真であることを明らかにすることによってフェルマーの小定理の証明にかえさせてもらう。
a＝1 のとき、1b を b で割った余りは 1 であリ、1 を b で割った余りに等しい。
a＝k のとき、kb を b で割った余りは、k を b で割った余りに等しいと仮定する。
a＝k＋1 のとき、(k＋1)b ＝ kb ＋ bＣ1kb−1 ＋ bＣ2kb−2 ＋ ・・・ ＋ bＣb−1k ＋ 1
bＣd ( 1 ≦ d ≦ b−1 ) は b の倍数なの（※）で、(k＋1)b を b で割った余りは kb＋1 になる。仮定（ kb を b で割った余りは k である ）より、(k＋1)b を b で割った余りは k＋1 になる。
a＝1 のとき「 b は a の約数でない素数である ならば ab を b で割った余りは a を b で割った余りに等しい 」という命題は真であった。よって、a＝2 のときもこの命題は真である。ということは、a＝3 のときもこの命題は真である。ということは、・・・・。以上の数学的帰納法によって、この命題が真であることが明らかになった。
（※）の証明：
d × bＣd ＝→ d×b! / {d!×(b−d)!} ＝→ d×b×(b−1)! / {d×(d−1)!×(b−d)!}
＝→ b × (b−1)! / [(d−1)!×{(b−1)−(d−1)}!] ＝→ b × (b−1)Ｃ(d−1)
よって、 (b−1)Ｃ(d−1) ＝ d × bＣd / b
b が素数で 1 ≦ d ≦ b−1 のとき、b と d は互いに素であり、(b−1)Ｃ(d−1) は自然数だから、bＣd は b の倍数である。
素数 b が a の約数である場合はどうだろうか？ たとえば、 33−1 ＝→ 9 確かに 3 で割った余りは 1 になっていない。 23−1 ＝→ 4 や 43−1 ＝→ 16 とは違う。なぜだろう？ 今日はここまで。
参考： 論理学 ＞ フェルマーの小定理につながる背理法による証明