オイラーの$\varphi$関数
合同式の1次方程式
\[
ax \equiv b \mod n
\]
は定義に戻れば、1次不定方程式
\[
ax - ny = b
\]
を考えていることになるから、解が存在するならば、ユークリッドの互除法で解くことができる。
しかし、ユークリッドの互除法では、明示的に解を表現しづらい。一方、「オイラーの$\varphi$関数」を用いると、
1次合同式の解を明示的に記述することができる。結論から述べると、次が成立する。
$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つに決まることが知られている。