オイラーの$\varphi$関数

合同式の1次方程式 \[ ax \equiv b \mod n \] は定義に戻れば、１次不定方程式 \[ ax - ny = b \] を考えていることになるから、解が存在するならば、ユークリッドの互除法で解くことができる。 しかし、ユークリッドの互除法では、明示的に解を表現しづらい。一方、「オイラーの$\varphi$関数」を用いると、 １次合同式の解を明示的に記述することができる。結論から述べると、次が成立する。
$a$と$n$が互いに素なとき \[ ax \equiv b \mod n \] の解は \[ x \equiv a^{\raise 5px {\varphi(n)-1}}\,b \mod n \] として得られる。（注：実際に計算するのは一般に大変。）

オイラー関数の定義

$1,2,\cdots,n$の中で$n$と互いに素な数の個数として、$\varphi(n)$を定義する。
例題. $\varphi(6)$を求めよ。
解. $\{1,2,3,4,5,6\}$ のなかで、$6$と互いに素な数は$\{1,5\}$の二つ。よって \[ \varphi(6)=2. \] 例. $\,\,$ $\varphi(1)=1. \quad \varphi(2)=1. \quad \varphi(3)=2. \quad \varphi(4)=2. \quad \varphi(5)=4.$

乗法的性質

自然数$a$と$b$が互いに素ならば、 \[ \varphi(ab) = \varphi(a)\cdot \varphi(b). \] 例題. $\varphi(12)$を求めよ。
解. $12 = 3\cdot 4$であり、$3$と$4$は互いに素である。 \[ \varphi(12)=\varphi(3\cdot 4) = \varphi(3)\varphi(4)=4. \]

明示公式

$n$の素因数分解を \[ n = p_1^{e_1}\cdots p_k^{e_k}\quad (e_1,e_2,\cdots,e_k\,\,\,\mbox{はすべて$1$以上.}) \] とするとき、次が成立。 \[ \varphi(n) = n \prod_{m=1}^k\left( 1- \frac{1}{p_m} \right) \] 例題. $\varphi(12)$を求めよ。
解. $12 = 2^2\cdot3$だから、素因数は$2$と$3$の二つだけ。 \[ \varphi(12)=12\cdot\left( 1-\frac{1}{2} \right)\left( 1-\frac{1}{3} \right) = (4-2)(3-1)=4. \]

オイラーの定理

$a$と$n$が互いに素であるとき \[ a^{\varphi(n)} \equiv 1 \mod n \] が成立する。

このオイラーの定理を用いると、合同式の解が明示的に表現できる。
$a$と$n$が互いに素とするとき次の合同式を考える。 \[ ax \equiv b \mod n \] この両辺に、$a^{\varphi(n)-1}$をかけると \[ a^{\raise 5px {\varphi(n)}} x \equiv a^{\raise 5px {\varphi(n)-1}}\,b \mod n \] が得られるが、オイラーの定理によって左辺$x$の係数は$1$として良い。

例. \[ 3x \equiv 1 \mod 23 \qquad (1) \] をオイラーの定理を用いて解く。(この方法は実際の計算としてはお勧めしない。)
$3$と$23$は互いに素であるからオイラーの定理により、 \[ 3^{\varphi(23)} \equiv 1 \mod 23 \] が成立。$\varphi(23)=22$だから \[ 3^{22} \equiv 1 \mod 23 \] が得られる。合同式(1)の両辺に$3^{21}$をかけると \[ x \equiv 3^{21} \mod 23 \] が得られる。この右辺を計算しよう。 \begin{alignat*}{2} 3^{21} = 3^{3\cdot7} = 27^7 &\equiv& 4^7 &\mod 23& \\ &=&\quad 4\cdot 4^3 \cdot 4^3 \\ &=&\quad 4 \cdot 64 \cdot 64 \\ &\equiv& \,\,4\cdot (-5) \cdot (-5) &\mod 23& \\ &\equiv& 8 &\mod 23&. \end{alignat*} 実際には、(1)の両辺に$8$をかければ良いのだから、この方法はとても効率が悪い。

演習問題

問題. $ 3^{2019} $を$10$で割ったあまりを求めよ。

解. $3$と$10$は互いに素だから、 オイラーの定理により \[ 3^{\varphi(10)} \equiv 1 \mod 10 \] が得られるが、$\varphi(10)=10(1-1/2)(1-1/5)=4$だから \[ 3^{4} \equiv 1 \mod 10. \] これを利用すれば \begin{alignat*}{2} 3^{2019}&=& \,\,\,3^{4\cdot 500 + 4\cdot4 +3} \\ &\equiv& 3^{3} &\mod 10 & \\ &\equiv& 7 &\mod 10 &. \end{alignat*}

問題. $ 2^{2019} $を$10$で割ったあまりを求めよ。
解. $2$と$10$は互いに素ではないから、直接オイラーの定理を使用できない。しかし、 $2$と$5$は互いに素だから、これについてはオイラーの定理が利用できる。 \[ 2^{\varphi(5)} \equiv 1 \mod 5. \] $\varphi(5)=4$だから \[ 2^{4} \equiv 1 \mod 5. \] したがって「$\hspace{-10px}\mod 5$」では、次のように計算できる。(本当に欲しいのは$\hspace{-5px}\mod 10$の結果.) \begin{alignat*}{2} 2^{2019}&=& \quad 2^{4\cdot 500 + 4\cdot4 +3} \\ &\equiv& 2^{3} &\mod 5& \\ &\equiv& 3 &\mod 5& \end{alignat*} よって \[ 2^{2019} \equiv 3 \mod 5 \] が得られた。また明らかに \[ 2^{2019} \equiv 0 \mod 2 \] であるから、問題は \[ \begin{cases} x = 0 \mod 2\\ x = 3 \mod 5 \end{cases} \] という連立合同式を解くことに帰着される。 これを解くと \[ x \equiv 8 \mod 10 \] が得られる。これで、当初の目的であった結果 \[ 2^{2019} \equiv 8 \mod 10 \] が得られたことになる。

Note. $\hspace{-5pt} \mod (pq)$を$\hspace{-5pt} \mod p$と$\hspace{-5pt} \mod q$に分解して考えるというのは、 整数論では常套手段。$p,q$が互いに素であるとき \[ \begin{cases} x = a \mod p\\ x = b \mod q \end{cases} \] の解は$\hspace{-5px} \mod (pq)$でただ1つに決まることが知られている。