tsujimotterのノートブック

日曜数学者 tsujimotter の「趣味で数学」実践ノート

「互いに素でない場合」のオイラーの定理

 m を正の整数としたとき、 a m互いに素な任意の整数として

 a^{\varphi(m)} \equiv 1 \pmod{m}

が成り立つことが知られています。 \varphi(m) はオイラーのトーシェント関数といって、この合同式はオイラーの定理として知られています。


これは素数を使った有名な暗号の一つ「RSA暗号」の理論的背景に使われます。具体的には、 m = pq として考えますが、 \varphi(m) = (p-1)(q-1) となります。上の定理から

 a^{k(p-1)(q-1)+1} \equiv a \pmod{m}

という合同式が成り立ちます。これを使うと、任意の  s に対して  t が存在して

 a^{st} \equiv a^{k(p-1)(q-1)+1} \equiv a \pmod{m}

が成り立つ事が言えます(ユークリッドの互除法を使います)。したがって、 s を暗号鍵、 t を複合鍵とすれば、 a を暗号化してまた戻してくる事ができるというわけですね。

以下の記事でより詳しく説明しました:
tsujimotter.hatenablog.com


ところで、意外にあまり明示的に書かれていない事実として、 a  m = pqと互いに素でなくても

 a^{\varphi(m)+1} \equiv a \pmod{m}

は成り立ちます。つまり、暗号文を選ぶ時に、わざわざ  m と互いに素であるかどうか気にしなくて良いというわけですね。

ちなみに、上が成り立つからといって両辺を  a で割った

 a^{\varphi(m)} \equiv 1 \pmod{m}

は一般に成り立ちません。両辺を割ることができない場合があるというのが、合同式の面白いところです。


互いに素とは限らないオイラーの定理の証明

それでは、ここでは以下の命題を証明します。

一般の  m ではダメで、 m = p_1 p_2 \cdots p_r のように、相異なる素数の積になっている場合に通用する証明です。面倒なので、 m = pq の場合だけで証明しますが、 r 個の場合もまったく同様に証明可能です。

命題1
 m = pq を相異なる素数  p, q の積とする。 a m互いに素とは限らない整数とし k を自然数とする。このとき、次が成り立つ:
 a^{k\varphi(m)+1}  \equiv a \pmod{m}


(証明)
 a^{k\varphi(m)+1} - a p で割り切れることを示すために、 a p で割り切れる場合と、そうでない場合に場合分けして考える。

(i)  p \mid a の場合:

明らかに

 a^{p-1} \equiv 0 \pmod{p}

である。両辺  k(q-1) 乗すると

 a^{k(p-1)(q-1)} \equiv 0 \pmod{p}

であり、両辺  a をかけて

 a^{k(p-1)(q-1)+1} \equiv 0 \equiv a \pmod{p}

が成り立つ。したがって、 \varphi(m) = (p-1)(q-1) より  p \mid  a^{k\varphi(m)+1} - a が得られる。

(ii)  p \not\mid a の場合:

フェルマーの小定理より

 a^{p-1} \equiv 1 \pmod{p}

である。両辺  k(q-1) 乗すると

 a^{k(p-1)(q-1)} \equiv 1 \pmod{p}

であり、両辺  a をかけて

 a^{k(p-1)(q-1)+1} \equiv a \pmod{p}

が成り立つ。したがって、 \varphi(m) = (p-1)(q-1) より  p \mid  a^{k\varphi(m)+1} - a が得られる。


以上 (i), (ii) の議論より、いずれの場合も  p \mid a^{k\varphi(m)+1} - a である事がわかった。

同様の議論を  q に対しても行うと、  q \mid a^{k\varphi(m)+1} - a がわかる。

したがって、  a^{k\varphi(m)+1} - a p でも  q でも割り切れるので、

 pq  \mid  a^{k\varphi(m)+1} - a

が言えたことになる。すなわち

 a^{k\varphi(m)+1} \equiv a \pmod{pq}

が示された。

(証明終わり)


類似例:カーマイケルの定理

実はカーマイケルの定理も、同様の事実を示す事ができます。

カーマイケル数  \lambda(m) の定義と、カーマイケルの定理は次の記事で思い出してください。
tsujimotter.hatenablog.com


すなわち、次が成り立つというわけです。

命題2
 m = pq を相異なる素数  p, q の積とする。 a m互いに素とは限らない整数とし k を自然数とする。このとき、次が成り立つ:
 a^{k\lambda(m)+1}  \equiv a \pmod{m}


証明は書かないですが、 \lambda(pq) = \operatorname{LCM}(p-1, q-1) なので、 (p-1)(q-1) のところをこれに置き換えればそのまま証明できる感じです。

今回のきっかけ

鯵坂もっちょさんの次のツイートがきっかけです:


たとえば、 a^7 \pmod{42} とかを考えると、一直線に右肩上がりになっているように見えます。これは

 a^7\equiv a \pmod{42}

を意味するのですが、上で示した「カーマイケルの定理の拡張(命題2)」が背景にあります。

実際、 m = 42 = 2 \cdot 3 \cdot 7 とすると、

 \lambda(42) = \operatorname{LCM}(\lambda(2), \lambda(3), \lambda(7)) = \operatorname{LCM}(1, 2, 6) = 6

となり、 42 と互いに素とは限らない  a に対して

 a^{6+1}\equiv a \pmod{42}

が成り立つというわけなんですね。

面白いです!

それでは今日はこの辺で!