33

第9章
9.1

フェルマー，オイラーの定理

フェルマーの定理

本章の目的は，整数のベキ乗数 an の法 m におけるふるまいを考察することである． 素数を法とする場合から始めよう．
定理 9.1 (フェルマーの定理) p を素数とし，a を p と互いに素な整数とすると，ap−1 ≡ 1 (mod p)が成り立つ．
××

証明 写像 fa : (Z/pZ) → (Z/pZ) を fa (x) = ax によって定義する． a が p を法として可逆であることに注意すれば，fa が全単射であることが確認できる． したがって，(p − 1)! =p−1
Yx≡

x=1

p−1
Y(ax) = ap−1 · (p − 1)! (mod p).

x=1

ここで p は素数だから，(p − 1)! は p を法として可逆，よって定理の合同式を得る． □この定理は「フェルマーの小定理」ともよばれる（「フェルマーの最終定理」と区別するため）．
例 9.2 フェルマーの定理を用いると累乗の計算が簡単になることがある． たとえば，56789
は素数 59 を法として以下のように計算できる． フェルマーの定理より 558 ≡ 1 (mod 59)が成り立つことに着目して，6789 の 58 による割り算 6789 = 117 · 58 + 3 を用いれば，56789 = (558 )117 · 53 ≡ 53 = 125 ≡ 7 (mod 59) となる．

9.2

フェルマーテスト

フェルマーの定理に現れる合同式は，p が素数であるための必要条件を与えているが，十分条件というわけではない． たとえば，414 ≡ 1 (mod 15), 1948 ≡ 1 (mod 49) であるが，15, 49 のどちらも素数ではない． しかし，多くの a について合同式が成り立てば十分条件にもなり得るかもしれない，と（ダメ元で）考えてみよう．

34
定義 9.3 n を 2 以上の自然数とする． 整数 a が an−1 ≡ 1 (mod n) をみたすとき，nを底 a に関する確率的素数という．
フェルマーの定理から，ひとつの底に関して確率的素数になっていなければ合成数である． たとえば，2220 ≡ 16 6≡ 1 (mod 221) だから 221 は素数ではない． 一方，十分多くの底に関して確率的素数であるならば，素数である可能性は高いと考えられる． 例として

229338 ≡ 329338 ≡ 529338 ≡ 729338 ≡ 1129338 ≡ 1 (mod 29339),（こいつら，どうやって計算すんだよ！ という疑問はごもっとも． 時間があれば講義で説明しましょう．
）したがって，29339 は底 2, 3, 5, 7, 11 に関する確率的素数であり，実際に素数であることが確かめられる．このような素数判定法（別の言い方をすれば，合成数を排除するための方法）をフェルマーテストという．
フェルマーテストはプログラムも簡単で計算も速く有用であるが，完全な素数判定法ではない． たとえば，n = 29341 は，底 2, 3, 5, 7, 11 に関する確率的素数であるにもかかわらず，13|n より素数ではないことが確認できる． 2002 年にフェルマーテストを改良した
AKS 素数判定法が発表され脚光を浴びたが，詳しくは別の機会に…ね．

9.3

オイラーの定理法 m が素数ではないとき，フェルマーの定理で述べられていることはそのままの形では一般に成り立たないことに注意する． たとえば，56−1 ≡ 5 6≡ 1 (mod 6), 29−1 ≡ 4 6≡ 1(mod 9), etc... フェルマーの定理を，法 m が合成数である場合にも適用できるように一般化するには，aN ≡ 1 (mod m) をみたすベキ指数 N を，m に関連付けて探さなければならない． その際，aN = a · aN −1 ≡ 1 (mod m) より，a は m を法として可逆，したがって定理 5.9 から，a, m は互いに素でなければならないことに注意する．
一般の合成数を考える前に，まず m が素数ベキの場合を考えよう．
補題 9.4 p を素数とし，a を p と互いに素な整数とすると，任意の自然数 n に対して

a(p−1)pn−1≡ 1 (mod pn )が成り立つ．
証明 n に関する数学的帰納法を用いる． n = 1 のときはフェルマーの定理そのものであn−1= 1 + pn k (k ∈ Z)
り，すでに示されている． n のとき成り立つと仮定すると，a(p−1)pと書ける． これを p 乗すれば，n + 1 ≤ 2n < 3n < · · · に注意して(p−1)pna= (1 + p k) = 1 + p · p k +npnpXp Cj pk ≡ 1 (mod pn+1 ).

jn jj=2

これは n + 1 のときに成り立つことを示している．

□35
ここで，定理 8.6（または補題 8.7）によれば，φ(pn ) = (p − 1)pn−1 だから，補題 9.4 のn
合同式は aφ(p ) ≡ 1 (mod pn ) と書き換えることができる． これをふまえて，フェルマーの定理は次の定理に拡張される．
定理 9.5 (オイラーの定理) 自然数 m > 1 と互いに素な任意の整数 a に対してaφ(m) ≡ 1 (mod m)が成り立つ．
証明 m を素因数分解して m = pn1 1 · · · pnr r (ただし，pj たちは相異なる素数で nj > 0)
njnとする． pj は a を割らないから，補題 9.4 より aφ(pj ) ≡ 1 (mod pj j ) を得る． 一方，nn
補題 8.8 より φ(m) は φ(pj j ) の倍数だから，aφ(m) ≡ 1 (mod pj j ) が各 j に対して成り立つことになり，これからただちに定理が導かれる．
□n

この証明において，φ(pj j ) たちの最小公倍数を ψ(m) とすれば，aψ(m) ≡ 1 (mod m)nが成り立つこともわかる． 一方，φ(m) は φ(pj j ) たちの公倍数なので ψ(m)|φ(m)，したがって，この合同式はオイラーの定理の精密化を与えていることになる．

9.4

位数

フェルマー，オイラーの定理では，法 m で 1 と合同になるためのベキ指数として φ(m)が採用されているが，前節の最後でも見たように φ(m) より小さいベキでも 1 と合同になる可能性がある． そのようなベキを特徴付けるために次の定義を導入する．
定義 9.6 m を 2 以上の自然数とする． m と素な整数 a に対して

ak ≡ 1 (mod m)をみたす最小の自然数 k を法 m に関する a の位数という． また，剰余類 α ∈(Z/mZ)× に対して α に属する元の法 m に関する位数はすべて等しい． それを α の位数という．
つまり，整数 a の法 m に関する位数とはmin k ∈ N ak ≡ 1 (mod m)= min k ∈ N ak = 1であり，これを簡単に剰余類 a の位数というわけである． なお，m と素でない整数 a の位数は定義されないことに注意しよう．

36
命題 9.7 m を 2 以上の自然数，a を m と互いに素な整数，s を法 m に関する a の位数とする． 自然数 r がar ≡ 1 (mod m)をみたすならば，位数 s は r の約数である． とくに s|φ(m) が成り立つ．
証明 r を s で割り算して，r = us + v, (0 ≤ v < s) とすると，1 ≡ ar = (as )u av ≡ av(mod m) だから，もし v > 0 とすると位数 s の最小性に矛盾する． よって v = 0 であり r = us は s の倍数である．
□
例 9.8 φ(100) = 40 だからオイラーの定理より，340 ≡ 1 (mod 100)． したがって，命題9.7 によれば，100 を法とする 3 の位数は 40 の約数 1, 2, 4, 5, 8, 10, 20, 40 のどれかである． 根気よく（そしてちょっと工夫して）計算すれば，38 6≡ 1, 310 6≡ 1 (mod 100) かつ320 ≡ 1 (mod 100) が得られ，位数は 20 であることがわかる．

命題 9.9 m を 2 以上の自然数，a を m と互いに素な整数，s を法 m に関する a の位数とする．

(1) s = uv (u, v ∈ N ) ならば，法 m に関する au の位数は v である．
(2) t ∈ N が s と互いに素ならば，法 m に関する at の位数も s である．
証明 簡単のため α = a = a + mZ とおき，1 = 1 + mZ も 1 と略す． したがって，たとえば αs = 1 となる． いま，a, m は互いに素なので α は可逆であり，α−1 が定義されることにも注意せよ．
(1) まず (αu )v = αuv = αs = 1 が成り立つ． よって，w を αu の位数とすると，命題 9.7
より w|v ． 一方，αuw = 1 だから，再び命題 9.7 より s = uv は uw の約数であり v|w．
ゆえに w = v ．
(2) まず (αt )s = (αs )t = 1 が成り立つ． よって，w を αt の位数とすると，命題 9.7 より w|s． いま，s, t は互いに素だから，sx + ty = 1 (x, y ∈ Z) と書けて，α = αsx+ty =(αs )x (αt )y = (αt )y ． 一方，αtw = 1 だから αw = (αt )yw = 1，したがって，再び命題 9.7
より s|w となるから，w = s を得る．
□
命題 9.10 m を 2 以上の自然数，a, b をともに m と互いに素な整数とする． 法 mに関する a, b のそれぞれの位数 s, t が互いに素ならば，法 m に関する ab の位数はst である．
×

証明 前命題の証明と同様に，α = a, β = b ∈ (Z/mZ) とする． w を αβ の位数とする． まず，(αβ)st = (αs )t (β t )s = 1 なので，命題 9.7 より w|st が成り立つ． そこで，逆に st|w を確かめればよい． まず，s, t は互いに素なので sx + ty = 1 をみたす x, y ∈ Zがとれる． このとき，αs = β t = 1 に注意すれば，α = αsx+ty = αty = (αβ)ty ． よって，αw = (αβ)wty = 1 となるから，再び命題 9.7 より s|w である． α, β の役割を入れ換えれば，t|w もわかる． s, t は互いに素なので，結局 w は st の倍数となる．
□