拡張Eulerの定理(互いに素ではない場合) ARC113-B A^B^C

ARC113のB問題は $A^i \equiv m_i \pmod{10},$ $B\, {}^j \equiv n_j \pmod{4}$ としたとき $m_i$ の列が4(の約数)の周期で循環すること、 $n_j$ の列が2(の約数)の周期で循環することを利用する問題でした。これらについては実際に実験して求めた人やFermatの小定理やEulerの定理によって説明しようとした人などがいました。しかしこれらの説明は $a^b \equiv c \pmod{d}$ とした時、 $d$ が素数である(Fermat)か、 $\gcd(a,\,d)=1$ である(Euler)ときについてしか説明することができません。ここでは互いに素ではない場合に拡張できるのではないかということで、それについて書いていきたいと思います。

前提知識
$n$が素数の場合
$n$のどの素因数の指数も1以下の場合
一般の場合
結論

前提知識

記法

$\gcd(n,\,m)$ とは $n$ と $m$ の最大公約数(Greatest Common Divisor)です。 $\gcd(n,\,m) = 1$ のとき、 $n$ と $m$ は互いに素と言います。

$a \equiv b \pmod{n}$ とは2整数 $a,\,b$ を $n$ で割った時の余りが等しいことを意味します。 $a$ や $b$ が整数でない場合にも拡張することができたりしますが、ここでは触れません。

$\displaystyle\prod$ は総乗記号で $\displaystyle\sum$ の掛け算バージョンです。 $\displaystyle\sum$ がS(和: sumの頭文字)に対応するギリシア文字σの大文字Σに由来するのに対し、 $\displaystyle\prod$ はP(積: productの頭文字)に対応するギリシア文字πの大文字Πに由来します。

中国剰余定理

中国剰余定理*1とは、 $k$ 個の整数 $n_i$ $(i = 1,\,2,\,\dots,\,k)$ がどの2数を選んできても互いに素であるとき $k$ 元の連立合同方程式 $$ x \equiv a_i \pmod{n_i} $$ を満たすような整数 $x$ が $\displaystyle\prod_{i=1}^{k} n_i$ を法として唯1つ存在するという定理です。 $n_i$ 同士が互いに素でなくともいいように拡張できますが、今回は互いに素である場合に限っても大丈夫です。詳しくはこちらを参照してください。
これから、全ての $n_i$ で $x \equiv y \pmod{n_i}$ となるとき、 $x \equiv y\ \displaystyle\left(\mathrm{mod}\ \prod_{i=1}^{k} n_i\right)$ となることが分かります。

Fermatの小定理、Eulerの定理、Carmichaelの定理

Fermat*2の小定理は $p$ を素数とし、 $a$ を $p$ の倍数でない整数としたとき $$ a^{p-1} \equiv 1 \pmod{p} $$ が成り立つというものです。

Euler*3の定理とCarmichael*4の定理はある函数 $f(n)$ が存在し、 $\gcd(a,\,n) = 1$ である2整数 $a,\,n$ について $$ a^{f(n)} \equiv 1 \pmod{n} $$ が成り立つというもので、Eulerの定理では $f(n)$ はEulerのトーシェント函数 $\varphi(n)$ 、Carmichaelの定理ではCarmichael函数 $\lambda(n)$ と呼ばれるものとなっています。

Eulerのトーシェント函数 $\varphi(n)$ は $1$ 以上 $n$ 以下の整数のうち $n$ と互いに素であるような数の個数を与える函数で、 $p$ が素数であるとき $\varphi(p) = p - 1$ となるため、Eulerの定理はFermatの小定理を素数に限らない場合に拡張したものとなっていると言えます。また、Carmichael函数 $\lambda(n)$ が返す値は $\varphi(n)$ の約数となっています。
また、トーシェント函数は互いに素な2数 $n,\,m$ について $\varphi(nm)=\varphi(n)\varphi(m)$ となることが知られています。
これらの定理についての証明や詳しい説明はこちらをどうぞ。

題名を拡張Eulerの定理としているため、 $f(n) = \varphi(n)$ として書きますが、それを $\lambda(n)$ に書き換えればCarmichaelの定理についても同じように拡張することができます*5。

では、 $a^i \equiv m_i \pmod{n}$ の周期性についてみていきましょう。ここで整数 $k$ を用いて $a = nk + m_1$ と表すことができ、 $$ (nk + m_1)^i = \sum_{j=0}^{i} {}_i \mathrm{C}_j\ (nk)^{i-j} {m_1}^j = (\text{$n$ の 1 乗以上の項}) + {m_1}^i $$ であり、全ての項の係数は整数であるため、 $0 \leq a \lt n$ の場合のみ考えるだけで十分であることが分かります。

$n$が素数の場合

$a \neq 0$ のとき、Fermatの定理より $a^{n-1} \equiv 1 \pmod{n}$ であることから $a^{i + (n-1)} \equiv a^{i} \pmod{n}$ であることが分かり、 $m_i$ の周期が $n-1$ であることが分かります。これはどの $a$ についても成立します。しかし、全ての $a$ について周期の最小値が $n - 1$ であるとは限りませんが、 $n - 1$ より小さな周期を持っていた場合、その周期は $n - 1$ の約数となっています。
$a = 0$ の時は常に $a^i \equiv 0$ となるため、周期は $1$ であり、 $n - 1$ の約数です。
例として $n = 5$ としてみます。このとき剰余は $$\begin{align}
&0: 0 \rightarrow 0 \rightarrow \cdots
\\&1: 1 \rightarrow 1 \rightarrow \cdots
\\&2: 2 \rightarrow 4 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow \cdots
\\&3: 3 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow \cdots
\\&4: 4 \rightarrow 1 \rightarrow 4 \rightarrow \cdots
\end{align}$$ となり、 $a = 0,\,1$ のとき周期 $1$ 、 $a = 4$ のとき周期 $2$ 、 $a = 2,\,3$ のとき周期 $4$ となっています。いずれも $4 = 5-1$ の約数ですね。

$n$のどの素因数の指数も1以下の場合

$p_i$ を $i$ 番目の素数とし、 $S$ を有限個の正整数を要素とする集合として、 $n = \displaystyle \prod_{i \in S} p_i$ と素因数分解できる場合です。 $a = q\ \displaystyle\prod_{i \in S} {p_i}^{e_i}$ とします。ここで $\gcd(n,\,q) = 1$ です。
このとき、 $a^{\varphi(n)} = q^{\varphi(n)}\ \displaystyle\prod_{j \in S} ({p_j}^{e_j})^{\varphi(n)}$ となり、各 $i$ について $\varphi(n) = \varphi(p_i) \displaystyle\prod_{j \in {S \setminus \{i\}}} \varphi(p_j)$ であり、 $t_i = \displaystyle\frac{\varphi(n)}{\varphi(p_i)} = \prod_{j \in {S \setminus \{i\}}} \varphi(p_j)$ とします。 $\bmod p_i$ としてEulerの定理より $q^{\varphi(n)} = \left(q^{t_i}\right)^{\varphi(p_i)} \equiv 1$ 、 $\left({p_j}^{e_j}\right)^{\varphi(n)} = \left({p_j}^{t_ie_j}\right)^{\varphi(p_i)} \equiv 1\ (i \neq j)$ となるため、 $$ a^{\varphi(n)} \equiv \left\{
\begin{array}{ll}
0 & (e_i \geq 1)\\
1 & (e_i = 0)
\end{array}
\right. $$ となり、$$ a^{k + \varphi(n)} \equiv \left\{
\begin{array}{ll}
0 & (e_i \geq 1)\\
a^k & (e_i = 0)
\end{array}
\right. $$ となりますが、 $e_i \geq 1$ のときはそもそも $a \equiv 0$ であるため、こちらでも $a^{k + \varphi(n)} \equiv a^k$ となることが分かります。

さて、ここまでの議論は $S$ 内の全ての $i$ について成り立つため中国剰余定理より $a^{k + \varphi(n)} \equiv a^k \pmod{n}$ であることが分かり、 $\gcd(a,\,n) = 1$ であるかどうかにかかわらず、その周期が $\varphi(n)$ であることが分かります。ARC113-Bでは $n = 10$ で、この時の剰余系は $$\begin{align}
&0: 0 \rightarrow 0 \rightarrow \cdots
\\&1: 1 \rightarrow 1 \rightarrow \cdots
\\&2: 2 \rightarrow 4 \rightarrow 8 \rightarrow 6 \rightarrow 2 \rightarrow \cdots
\\&3: 3 \rightarrow 9 \rightarrow 7 \rightarrow 1 \rightarrow 3 \rightarrow \cdots
\\&4: 4 \rightarrow 6 \rightarrow 4 \rightarrow \cdots
\\&5: 5 \rightarrow 5 \rightarrow \cdots
\\&6: 6 \rightarrow 6 \rightarrow \cdots
\\&7: 7 \rightarrow 9 \rightarrow 3 \rightarrow 1 \rightarrow 7 \rightarrow \cdots
\\&8: 8 \rightarrow 4 \rightarrow 2 \rightarrow 6 \rightarrow 8 \rightarrow \cdots
\\&9: 9 \rightarrow 1 \rightarrow 9 \rightarrow \cdots
\end{align}$$ となり、周期は $4$ ですがこれは $\varphi(10) = 4$ であるためです。

一般の場合

$n = \displaystyle\prod_{i \in S} {p_i}^{d_i}\ (d_i \leq 1)$ と素因数できるとします。 $a$ については上の場合と同様 $a = q\ \displaystyle\prod_{i \in S} {p_i}^{e_i}$ とします。
各 $p_i$ について $k \geq d_i$ のとき ${p_i}^k \equiv 0 \pmod{{p_i}^{d_i}}$ となります。 $a^k = q^k {p_i}^{ke_i} \displaystyle\prod_{j \in {S \setminus \{i\}}} ({p_j}^{e_j})^k$ であるため、 $e_i \neq 0$ であるとき $k \geq d_i \displaystyle\left(\geq \left\lceil\frac{d_i}{e_i}\right\rceil\right)$ とすると $a^k \equiv 0 \pmod{{p_i}^{d_i}}$ となります。よって $k \geq \displaystyle\max_{i \in S} d_i$ のときに上の場合と同様の議論で全ての $i$ について $a^{k + \varphi(n)} \equiv a^k \pmod{{p_i}^{d_i}}$ が成り立ちます。よって、中国剰余定理より $a^{k + \varphi(n)} \equiv a^k \pmod{n}$ であることが分かり、 $\gcd(a,\,n)=1$ であるかどうかにかかわらず、その周期が $\varphi(n)$ であることが分かります。上の場合と違うのはループに入る前の部分があることがある、というところです。例えば $n = 24,\,a = 14$ とすると、その剰余は $$\begin{align}
14 \rightarrow 4 \rightarrow 8 \rightarrow 16 \rightarrow 8 \rightarrow \cdots
\end{align}$$ となり、 $8 \rightarrow 16$ という周期 $2$ の循環となっていますが、そのループに入る前に $14 \rightarrow 4$ という部分が出てきています。これは素因数 $2$ の指数が $24$ と同じ $3$ になるまではループに入らないことに起因します。
ARC113-Bでの $n = 4$ で周期 $2$ となったのは $\varphi(4) = 2$ であるからです。

結論

一般の場合についての説明がすこしグダグダしてしまいましたが、Eulerの定理の拡張として $a^i \equiv m_i \pmod{n}$ となる $0 \leq m_i \lt n$ は、 $n$ と $a$ が互いに素であるかどうかにかかわらず周期 $\varphi(n)$ で循環することが分かりました。但し、 $n$ に指数が2以上であるような素因数を持つ場合は $a$ によっては最初の1乗, 2乗,... あたりはループに入らないこともあります。しかし、十分に指数を大きくすると周期 $\varphi(n)$ で循環します。

*1:中国の剰余定理、中国式剰余定理、孫子の定理とも

*2:仏[fɛʁma]: フェルマー(Pierre de Fermat) 最終定理の人

*3:瑞独[ˈɔɪləɹ]: オイラー(Leonhard Euler) 色々な公式を作った人

*4:米英/ˈkɑˌrmaɪkʌl/ : カーマイケル(Robert Carmichael)

*5:トーシェント函数の乗法的である性質を用いているところがあります。Carmichael函数では積ではなく最小公倍数が対応し、それによってうまく読み替えてやることが必要になります