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

$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 \equiv 0 \pmod{p}$ なので、両辺 $k\varphi(m)+1$ 乗して

$a^{k\varphi(m)+1} \equiv 0 \pmod{p}$

が成り立つ。 $a \equiv 0 \pmod{p}$ より

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

が言える。したがって、 $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)$ のところをこれに置き換えればそのまま証明できる感じです。

今回のきっかけ

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

n^a mod b (0≦n≦b)をaとb変化させながら見てみた（冪剰余）けどいろいろ面白いな。たまにy=xの直線上に乗ってるのなんだろ
（フェルマーの小定理っぽいかと思ったけどn^7 mod 42 = nとかになってるので微妙に違いそう） pic.twitter.com/XuaeQDv4Yl
— 鯵坂もっちょ🐟 (@motcho_tw) 2021年1月22日