用
考え方(1) mbと nbをaで割った余りが等しいとすると矛盾が生じることを示す。
(1) 正の整数aとbが互いに素のとき、 b, 26, 3b, 4b, ………, (a-1)b
例 題 277
フェルマーの小定理(1)O
をaで割った余りは,すべて異なることを示せ,ただし, aN3 と
する。
vo(1)を利用して,正の整数aが3以上の素数かと互いに素であるなら
ば、aP-! をかで割った余りは1であることを示せ, 必要であれば,
bと m が互いに素のとき, ka=kb (modm) ならば,
a=b(mod m)となることを用いてもよい。
mbと nb をaで割った余りが等しいとすると矛盾が生じることを示す。
(2) 合同式を利用して,a°!=1 (modp) を示す。
「総答(1) m, n は整数で, 1lSm<n<aとして、 aで割ったと
きのmbと nb の余りが等しいと仮定する。
このとき,nb-mb=(n-m)b はaの倍数であるが, aとbは互いに素よ
り,n-mがaの倍数となる. ところが, 1<n-m<a-1 より, n-mはa
の倍数にならないので矛盾する。
よって,aで割った余りはすべて異なる。
(2)aとかは互いに素であるから, a, 2a, 3a, 4a, ……, (カー1)aをかで割っ
たときの(カ-1)個の余りは, (1)よりすべて異なり,かは素数であるから,
(カ-1)個の余りは, 1, 2, 3, 4, ……, p-1である。
したがって,pを法とする合同式を用いると,
a×2a×3a×4a×………×(カー1)a
=1×2×3×4× ×(カ-1) (mod)
つまり,
素数かと 2,3, 4.
背理法を利用する。
あケ素が4 ポー
4お(1-
a=b(modm),
c=d (modm)
ならば、
ac=bd (modm)
(b-1)!a°-1=(カ-1)! (modp) 0
……, p-1とはいずれも互いに素
るるっであるから,(カー1)! とかは互いに素で, ①は,
a-1=1 (modか)
で働多(よって, a"-1 をかで割った余りは1である。
p=2 のときも成り
立つ、
