参考資料7

代数学入門参考資料 7
2015 年度後期
工学部・未来科学部 1 年
担当: 原隆 (未来科学部数学系列・助教)
§ 合同式 (続)
■フェルマーの小定理定理 (フェルマーの小定理 Fermat’s little theorem)
p を素数とし、a を a ̸≡ 0 (mod p) を満たす整数とする*1 。このとき ap−1 ≡ 1 (mod p)
が成り立つ。
babababababababababababababababababab
p を素数とするとき、a ̸≡ 1 (mod p) を満たす整数 a には法 p の逆元が存在する。
系
つまり ma ≡ 1 (mod p) を満たす整数 m が存在する。
【証明】 m = ap−2 とおくと、フェルマーの小定理より
ma = ap−2 a = ap−1 ≡ 1 (mod p)
□
となる。
注: − フェルマーの小定理により、保留にしていた逆元の存在定理が法が素数の場合には証明
出来た。それでは法が合成数の場合はどうすれば良いであろうか? その場合は、フェル
マーの小定理を拡張したオイラーの定理を用いることで、やはり逆元の存在定理を証明する
ことが出来る。詳細は次回以降に扱います。
− この定理は、1640 年にピエール・ド・フェルマー Pierre de Fermat
が友人のベルナルド・フレニクル・ド・ベシー Bernard Frenicle
de Bessy に宛てて出した手紙の中で紹介されたものであるが、実
はフェルマー自身が証明を付けたわけではない。この定理の証明
は、時代を下ってライプニッツやオイラーによって付けられるこ
ととなった。「フェルマーの小定理」の呼称は、クルト・ヘンゼル
ピエール・ド・フェルマー
Kurt Hensel による整数論の教科書である Zahlentheorie (ドイツ
Pierre de Fermat
語「で整数論」の意味) の中で始めて用いられたようである。勿論「小定理」とわざわざ冠さ
れているからには「フェルマーの大定理」と呼ばれるものもあるわけだが、それは「n が 3 以
上の自然数のとき、xn + y n = z n を満たす (x, y, z) = (0, 0, 0) 以外の整数組は存在しない」
ことを主張する所謂フェルマーの最終定理 Fermat’s last theorem のことである。
*1
つまり a は p で割り切れない整数ということ。
babababababababababababababababababab
系 (ウィルソンの定理)
p を 0 でない整数とするとき、合同式
(p − 1)! ≡ −1 (mod p)
が成り立つための必要十分条件は p が素数であることである。
【証明】
ジョン・ウィルソン
John Wilson
p が素数のとき (p − 1)! ≡ −1 (mod p) が成り立つことのみ示す。逆側の主張はテキスト
『数の不思議』の p. 152 を参照すること。
先ず f (x) = xp−1 − 1 とおくと、フェルマーの小定理より
f (1) ≡ 0 (mod p),
f (2) ≡ 0 (mod p),
f (p − 1) ≡ 0
(mod p)
(g(x) は多項式)
· · · (∗)
......,
が成り立つ。したがって因数定理の mod p 版*2 より
xp−1 − 1 ≡ (x − 1)(x − 2) · · · (x − p + 1)g(x) (mod p)
が成り立つが、両辺の xp−1 の係数を比較して g(x) ≡ 1 (mod p) となることが分かる。そこで (∗)
に g(x) ≡ 1 (mod p) と x ≡ 0 (mod p) を代入すると
−1 ≡ (−1) · (−2) · · · · · · · (−p + 1)
(mod p) ≡ (−1)p−1 (p − 1)!
(mod p)
が得られる。p が奇素数のときは p−1 は偶数なので (−1)p−1 = 1 となり、所望の合同式 (p−1)! ≡ −1
(mod p) が得られる。p = 2 のときは (−1)2−1 = −1 ≡ 1 (mod 2) に注意すれば良い。
□
■演習問題問題 7-1. (フェルマーの小定理の証明のアイデア)*3
以下の設問に答えなさい。
(1) mod 3, mod 5, mod 7 での「
の表」を完成させなさい。特に各行、各列には
掛け算
1, 2, . . . , p − 1 (p = 3, 5, 7) が一度ずつ登場していることを確認しなさい。
(2) 特に「a の段」(1 ≤ a ≤ p − 1) の行の数字を全て掛け合せることで、合同式
{1 · 2 · · · · · (p − 1)}(ap−1 − 1) ≡ 0 (mod p)
が成り立つことを示しなさい。
(3) (2) を用いて、p = 3, 5, 7 の場合のフェルマーの小定理 ap−1 ≡ 1 (mod p) を証明しなさい。
※ 一般の素数 p に対する証明方針も同様です。
問題 7-2. (逆元の計算)
以下の数の逆元をフェルマーの小定理を用いて計算しなさい。
(1)
*2
*3
5
(mod 7)
(2)
3
(mod 5)
テキスト『数の不思議』定理 20. を参照。
講義でも扱います。
(3) −2 (mod 11)
(4)
−3 (mod 13)
■参考: フェルマーの小定理の証明
定理 (フェルマーの小定理; 再掲)
p を素数とし、a を a ̸≡ 0 (mod p) を満たす整数とする。このとき ap−1 ≡ 1 (mod p)
が成り立つ。
babababababababababababababababababab
証明の方針
法 p での「掛け算の表」の各行、各列に 1, 2, . . . , p − 1 が 1 度ずつ現われることを示そう
⇝ 講義で説明したやり方で ap−1 ≡ 1 (mod p) が証明出来る。
【証明】
a ̸≡ 0 (mod p) を満たす整数 a を 1 つ固定しておく。
ステップ 1. 整数 x ̸≡ 0 (mod p), y ̸≡ 0 (mod p) に対して
x ̸≡ y (mod p) ならば ax ̸≡ ay (mod p) が成り立つ
ことを示す*4 *5 。
もし ax ≡ ay (mod p) となっていたとすると、移項して a(x − y) ≡ 0 (mod p) が成り立つ。
つまり a(x − y) が p の倍数ということになる。ここで a と p は互いに素なので、(素因数
分解を考えると) x − y が p の倍数になっていなければならない。これは x ≡ y (mod p) が
成り立つことを意味しており、x ̸≡ y (mod p) であったことと矛盾する。したがって背理法
により、 ax ̸≡ ay (mod p) が成り立つ。
ステップ 2. 整数 a · 1, a · 2, a · 3, . . . , a · (p − 1) は法 p で考えると 1, 2, 3, . . . , p − 1 の並べ替えと
なっていることを示す*6 。
先ず、全ての整数は法 p で 0, 1, 2, . . . , p − 1 の何れかと合同となることに注意しよう (「p で
割った余り」を考える)。ここで a 及び 1, 2, . . . , p − 1 は何れも p と互いに素なので、
a · 1, a · 2, . . . , a · (p − 1) は p の倍数ではないため、法 p で 1, 2, 3, . . . , p − 1 の何れかと合同
となる。さらにステップ 1. より、a · 1, a · 2, . . . , a · (p − 1) はどの 2 つも法 p で合同ではな
いので、a · 1, a · 2, . . . , a · (p − 1) は 1, 2, . . . , p − 1 の並べ替えとなっていなければならない。
ステップ 3. ステップ 2. より
(a · 1)(a · 2) · · · (a · (p − 1)) ≡ 1 · 2 · · · · · (p − 1) (mod p)
∴ (1 · 2 · · · · (p − 1))(ap−1 − 1) ≡ 0 (mod p)
が成り立つが、p と 1 · 2 · · · (p − 1) は互いに素なので、約分して ap−1 − 1 ≡ 0 (mod p)
を得る*7 。
□
*4
このステップは、法 p での掛け算の表の「a の段」に登場する数がすべて異なることを示していることに相当する。
*5
抽象数学の用語を用いると、このことは「(Z/pZ)× 上の a 倍写像が単射 injective である」ことを示していること
に他ならない。
このステップは、
「a の段」に 1, 2, . . . , p − 1 が一度ずつ現れることを示していることに相当する。
*7 演習問題 4-1. (1) 参照。
*6
【演習問題解答】
問題 7-1.
(1) 以下の通り。
1
2
3
4
5
6
1
2
3
4
1
1
2
3
4
5
6
1
2
1
1
2
3
4
2
2
4
6
1
3
5
1
1
2
2
2
4
1
3
3
3
6
2
5
1
4
2
2
1
3
3
1
4
2
4
4
1
5
2
6
3
4
4
3
2
1
5
5
3
1
6
4
2
6
6
5
4
3
2
1
mod 3
mod 5
mod 7
(2) 例えば mod 7 の表の「3 の段」の横の数を掛け合わせると、
(3 · 1)(3 · 2)(3 · 3)(3 · 4)(3 · 5)(3 · 6) ≡ 3 · 6 · 2 · 5 · 1 · 4
∴
(mod 7)
(1 · 2 · 3 · 4 · 5 · 6)(36 − 1) ≡ 0 (mod 7)
となる。どの表の他の行でも同様の計算が出来る (各自色々と計算してみよう!!)。
(3) (2) の例では、1 · 2 · · · · · 6 と法 7 は互いに素なので、演習問題 4-1. (1) により
36 − 1 ≡ 0
(mod 7)
∴
36 ≡ 1 (mod 7)
が従う (他の行でも同様)。
問題 7-2.
(1) フェルマーの小定理より 56 ≡ 1 (mod 7) が成り立つので、法 7 での 5 の逆元は
5−1 ≡ 55
(mod 7)
である。52 = 25 ≡ 4 (mod 7), 53 ≡ 4 · 5 ≡ 20 (mod 7) より、
5−1 ≡ 55 ≡ 52 · 53 ≡ 4 · 20 ≡ 80 ≡ 3 (mod 7)
となる。
(実際 5 · 3 = 15 ≡ 1 (mod 7) より、確かに 3 は法 7 での 5 の逆元である)
(2) フェルマーの小定理より 34 ≡ 1 (mod 5) が成り立つので、法 5 での 3 の逆元は
3−1 ≡ 33
(mod 5)
である。したがって
3−1 ≡ 33 ≡ 27 ≡ 2 (mod 5)
となる。
(実際 3 · 2 = 6 ≡ 1 (mod 5) より、確かに 2 は法 5 での 3 の逆元である)
(3) フェルマーの小定理より (−2)10 ≡ 1 (mod 11) が成り立つので、法 11 での −2 の逆元は
(−2)−1 ≡ (−2)9
(mod 7)
である。(−2)3 ≡ −8 ≡ 3 (mod 11) より、
(−2)−1 ≡ (−2)9 ≡ {(−2)3 }3 ≡ 33 ≡ 27 ≡ 5
(mod 11)
となる。
(実際 −2 · 5 = −10 ≡ 1 (mod 11) より、確かに 5 は法 11 での −2 の逆元である)
(4) フェルマーの小定理より (−3)12 ≡ 1 (mod 13) が成り立つので、法 13 での −2 の逆元は
(−3)−1 ≡ (−3)11
(mod 13)
である。(−3)2 ≡ 9 (mod 13), (−3)3 ≡ −27 ≡ −1 (mod 13) より、
(−3)−1 ≡ (−3)11 ≡ {(−3)3 }3 · (−3)2 ≡ (−1)3 · 9 ≡ −9 ≡ 4
(mod 13)
となる。
(実際 −3 · 4 = −12 ≡ 1 (mod 13) より、確かに 4 は法 13 での −3 の逆元である)

Download Report