オイラーの定理とカーマイケルの定理

この記事は, 旧ブログから移植された記事です. よって, その内容として, 旧ブログに依存した文脈が含まれている可能性があります. 予めご了承下さい.

以前の記事, エルガマル暗号では, エルガマル暗号に関する諸々の前提の説明と, その実装について示した. 同エントリ内で, フェルマーの小定理1については取り扱ったものの, その一般形であるオイラーの定理およびカーマイケルの定理について特に触れなかったため, 本エントリでそれらに関してまとめる. しばしば値の確認には, 簡単のため Haskell を使う.

オイラーの定理

いま, フェルマーテストを定義したとき, FTn(a)FT_n(a) をパスするには (すなわち, フェルマーの小定理が示す合同式が成り立つには), 要件として, 既約剰余類郡 Zn∗\mathbb{Z}^{\ast}_n の各要素と ∃a ∈Z^\exists a\ \in\mathbb{Z} の積が全て異なり,  mod n\bmod n の既約代表系のすべての積と合同でなければならない. たとえば, 法 n=8n=8 による合同関係で構成する剰余類の完全代表系2は 0,1,2,3,4,5,6,70,1,2,3,4,5,6,7 であるが, a=2a=2 としてしまうと, 既約剰余類郡が構成できていないので, 次のようにしても完全代表系が得られない(積をわざわざ示していないが, 非合同でないことは, 各要素の積が全て異なっていない時点で明白である).

Prelude> [x * 2 `rem` 8 | x <- [0..7]]
[0,2,4,6,0,2,4,6]

そこで, 先に述べた剰余類の既約代表系を考える. これは ϕ(8)=4\phi(8)=4 個3で, 1,3,5,71,3,5,7 である. これを同じように, {1⋅a, 3⋅a, 5⋅a, 7⋅a}\left\{1\cdot a,\ 3\cdot a,\ 5\cdot a,\ 7\cdot a\right\} とし, 先の要件を確認すると, この補題2より,  mod 8\bmod 8 で全体として {1,3,5,7}\left\{1,3,5,7\right\} と一致していて, 1⋅3⋅5⋅7≡1⋅3⋅5⋅7⋅a4(mod8)(1)1\cdot 3\cdot 5\cdot 7\equiv 1\cdot 3\cdot 5\cdot 7\cdot a^4\pmod{8}\tag{1} gcd⁡(1⋅3⋅5⋅7,8)=1\gcd(1\cdot 3\cdot 5\cdot 7,8)=1 だから, 1⋅3⋅5⋅71\cdot 3\cdot 5\cdot 7 を約して, a4≡1(mod8)(2)a^4\equiv 1\pmod{8}\tag{2} これは, gcd⁡(a,n)=1\gcd(a,n)=1 ということの他に, aa および nn の値に依存した論ではない. すなわち,

オイラーの定理

aϕ(n)≡1(modn) (2≤n∈Z+, gcd⁡(a,n)=1)a^{\phi(n)}\equiv 1\pmod{n}\ (2\leq n\in\mathbb{Z}^{+},\ \gcd(a,n)=1)

がいえる4.

*Main> euler'sTheorem n = [a `modExp` (totient n) $ n | a <- [2..], gcd a n == 1]
*Main> all (==1) $ take 100 $ euler'sTheorem 8
True

nn が素数 pp であるとき, ϕ(p)=p−1\phi(p)=p-1 で, フェルマーの小定理5となる6.

ラグランジュの定理

いま述べたオイラーの定理は, ラグランジュの定理を使っても証明できる. ラグランジュの定理は,

ラグランジュの定理

有限郡 GG の部分郡 HH の位数 ∣H∣\mid H\mid は, GG の位数 ∣G∣\mid G\mid の約数となる. ∣G∣ = ∣G:H∣∣H∣\mid G\mid\ =\ \mid G:H\mid \mid H\mid

である.

ラグランジュの定理

有限郡 GG の部分郡 HH による類別が G=⋃iraiH\displaystyle G=\bigcup_i^r a_iH であるとき, ∣G∣=r∣H∣\mid G\mid=r\mid H\mid といえる. この rr は r=∣G:H∣r=\mid G:H\mid そのものなので, ∣G∣ = ∣G:H∣∣H∣\mid G\mid\ =\ \mid G:H\mid\mid H\mid.

ごく直感的な定理である. これを使えば, オイラーの定理は次のように証明できる.

補題 1

有限郡 GG とその元 ∀g∈G^\forall g\in G に対し, g∣G∣=eg^{\mid G\mid}=e. e∈Ge\in G は単位元.

補題 1

巡回部分郡 H=<g>H=\lt g\gt の元 gg の位数 ∣H∣\mid H\mid は, 巡回して gi=eg^i=e となる最小の i∈Ni\in\mathbb{N} であるといえる. すなわち g∣H∣=eg^{\mid H\mid}=e ここで, 商集合の位数を両辺に次のように与える. (g∣H∣)∣G:H∣=(e)∣G:H∣(g^{\mid H\mid})^{\mid G:H\mid}=(e)^{\mid G:H\mid} 左辺は指数法則により, また右辺は単位元の繰り返しだから, これを次のようにかける. g∣H∣∣G:H∣=eg^{\mid H\mid\mid G:H\mid}=e ラグランジュの定理より g∣G∣=eg^{\mid G\mid}=e

オイラーの定理

オイラーの定理を仮定したとき, 脚注7より剰余類 a‾\overline{a} は法 nn に関する既約剰余類郡 Zn∗\mathbb{Z}^{\ast}_{n} に含まれる.
∣Zn∗∣=ϕ(n)\mid\mathbb{Z}^{\ast}_{n}\mid=\phi(n) だから補題 1 より a‾ϕ(n)=aϕ(n)‾=1‾\overline{a}^{\phi(n)}=\overline{a^{\phi(n)}}=\overline{1}.

カーマイケルの定理

オイラーの定理で用いる ϕ\phi 関数は, am≡1(modn) (m∈N,gcd⁡(a,n)=1a^{m}\equiv 1\pmod{n}\ (m\in{N}, \gcd(a,n)=1 を成立させる最小の整数 mm を持ち得ない. たとえば, n=8n=8 では, 先の通り確かに m=ϕ(8)=4m=\phi(8)=4 で合同式が満足できたが, m=2m=2 としても, これを満足できる.

*Main> all (==1) $ take 100 $ [a `modExp` 2 $ 8 | a <- [2..], gcd a 8 == 1]
True

カーマイケルの λ\lambda 関数は, 与えられた整数 nn に対して同合同式を満足する最小の mm を定義より自明に与える.

カーマイケルの λ\lambda 関数

扱う文字を全て整数とし, λ(n)\lambda(n) は λ(1):=1λ(2):=1λ(4):=4λ(2k):=ϕ(2k) (0≤k≤2)λ(2k):=2k−2=ϕ(2k)2 (e≥3)λ(ph):=ϕ(ph)=(p−1)⋅ph−1 (p is an odd prime,h≥1)λ(2kp1h1p2h2p3h3⋯ptht):=lcm(λ(2k),λ(p1h1),λ(p2h2),λ(p3h3),⋯ ,λ(ptht)) (pn is an odd prime,k≥0,hn≥1) \begin{array}{lcl} \lambda(1)&:=&1\\ \lambda(2)&:=&1\\ \lambda(4)&:=&4\\ \lambda(2^k)&:=&\phi(2^k)\ (0\leq k\leq 2)\\ \lambda(2^k)&:=&2^{k-2}=\dfrac{\phi(2^k)}{2}\ (e\geq 3)\\ \lambda(p^h)&:=&\phi(p^h)=(p-1)\cdot p^{h-1}\ (p\ is\ an\ odd\ prime, h\geq 1)\\ \lambda(2^kp_1^{h_1}p_2^{h_2}p_3^{h_3}\cdots p_t^{h_t})&:=&\mathrm{lcm}(\lambda(2^k),\lambda(p_1^{h_1}),\lambda(p_2^{h_2}),\lambda(p_3^{h_3}),\cdots,\lambda(p_t^{h_t}))\ (p_n\ is\ an\ odd\ prime, k\geq 0, h_n\geq 1) \end{array} と定義する.

カーマイケルの定理

aλ(n)≡1(modn) (2≤n∈Z+, gcd⁡(a,n)=1)a^{\lambda(n)}\equiv 1\pmod{n}\ (2\leq n\in\mathbb{Z}^{+},\ \gcd(a,n)=1)

実装して確かめてみる.

*Main> let carmichael'sLambda n = head [k | k <- [1..], and [(m `modExp` k $ n) < 2 | m <- [1..n] gcd m n < 2]]
*Main> let carmichael'sTheorem n = [a `modExp` (carmichael'sLambda n) $ n | a <- [2..], gcd a n == 1]
*Main> all (==1) $ take 100 $ carmichael'sTheorem 8
True

  1. 証明: フェルマーの小定理↩︎

  2. 補足. 郡 GG とその部分郡 HH があるとき, HH は郡であるから単位元 e∈He\in H を含む. よって, ∃a∈G^\exists a\in G の剰余類を aH={ah∣h∈H}aH=\left\{ah\mid h\in H\right\} としたとき(簡単のため, 左剰余類として式をおいたが, これに深い意味はない.), a=ae∈aHa=ae\in aH より a∈aHa\in aH である. この aa を剰余類 aHaH の代表という. また郡 GG は, 異なる aia_i を代表とした剰余類 aiHa_iH によって類別できる(G=⋃iaiH\displaystyle G=\bigcup_i a_iH). この ∣G:H∣\mid G:H\mid 個の類別に対して, 各剰余類から代表の元を取り, 構成した集合を, GG の HH に対する代表系という.↩︎

  3. ここで, ϕ\phi は, オイラーのトーシェント関数.↩︎

  4. コード内のtotientとmodExpは, それぞれ以前の投稿のうち, オイラーのトーシェント関数の実装部分と, カーマイケル数を得るための実装を利用.↩︎

  5. 証明: フェルマーの小定理↩︎

  6. この補足は冗長的かもしれないが, nn が素数 pp である場合, Zp∗\mathbb{Z}_p^{\ast} が構成されるから, これから取った代表は素数 pp と互いに素であることから, 既約代表である. この事実も, 一般に \(\) から \(\) へのような式変形が実行できることとの整合を示す.↩︎

  7. 補足. 郡 GG とその部分郡 HH があるとき, HH は郡であるから単位元 e∈He\in H を含む. よって, ∃a∈G^\exists a\in G の剰余類を aH={ah∣h∈H}aH=\left\{ah\mid h\in H\right\} としたとき(簡単のため, 左剰余類として式をおいたが, これに深い意味はない.), a=ae∈aHa=ae\in aH より a∈aHa\in aH である. この aa を剰余類 aHaH の代表という. また郡 GG は, 異なる aia_i を代表とした剰余類 aiHa_iH によって類別できる(G=⋃iaiH\displaystyle G=\bigcup_i a_iH). この ∣G:H∣\mid G:H\mid 個の類別に対して, 各剰余類から代表の元を取り, 構成した集合を, GG の HH に対する代表系という.↩︎

活動継続のためのご支援を募集しています