【徹底解説】オイラー関数の乗法的性質

本記事は数学の徹底解説シリーズに含まれます。

初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。

オイラー関数の乗法的性質

証明

$a,b$を法とする既約剰余系をそれぞれ

とおくと，既約剰余類の個数より$m{=}\varphi(a),n{=}\varphi(b)$となります。このとき，

を示すことができれば式($\ref{主題}$)が示されます。そこで，やや天下り的ですが$mn$組の連立一次合同式

\begin{cases}
x\equiv a_{i}\pmod{a}\\[0.7em]
x\equiv b_{i}\pmod{b}\label{連立方程式}
\end{cases}

を考えます。$a$と$b$が互いに素であることに注意すると，中国剰余定理より$ab$を法としてただ一つの解$c_{ij}$をもちます。この$c_{ij}$たちが$ab$を法とする既約剰余系の一つをなすことを示すことができれば，既約剰余類の個数より式($\ref{証明のテーマ}$)が示されます。そこで，以下では

1. $c_{ij}$が$ab$を法とする剰余類に重複して登場しないこと
2. $c_{ij}$が$ab$を法とする既約剰余類の一部をなしていること
3. $c_{ij}$が$ab$を法とする既約剰余類を網羅していること

の順番で証明を続けます。これらの命題を示すことができれば，$c_{ij}$たちが$ab$を法とする既約剰余系の一つをなすことが示され，式($\ref{証明のテーマ}$)が示されます。

$c_{ij}$が$ab$を法とする剰余類に重複して登場しないこと

$c_{ij}$が$ab$を法とする剰余類に重複して登場すると仮定すると，

となる$i,j,k,l$が存在します。このとき，$c_{ij},c_{kl}$が連立方程式($\ref{連立方程式}$)の解であることに注意すると，

\begin{cases}
a_{i}\equiv c_{ij} \equiv c_{kl} \equiv a_{k}\pmod{a}\\[0.7em]
b_{j}\equiv c_{ij} \equiv c_{kl} \equiv b_{l}\pmod{b}
\end{cases}

が得られますが，$a_{i},a_{k}$は$a$を法とする既約剰余系の要素として定義されていますので，$i{=}k$でなければなりません。同様に，$j{=}l$でなければなりません。以上より，$c_{ij}{=}c_{kl}$となるため，$c_{ij}$が$ab$を法とする剰余類に重複して登場しないことが示されました。

$c_{ij}$が$ab$を法とする既約剰余類の一部をなしていること

連立方程式($\ref{連立方程式}$)より，$c_{ij}$は

を満たすため，$c_{ij}$は$a$を法とする既約剰余類$R(a_{i})$に含まれます。すると，既約剰余類の定義より$c_{ij}$は$a$と互いに素となります。同様に，$c_{ij}$は$b$とも互いに素となります。よって，互いに素な整数からなる積の性質より$c_{ij}$は$ab$と互いに素となるため，$c_{ij}$は$ab$を法とする既約剰余類の代表元となります。これより，$c_{ij}$が$ab$を法とする既約剰余類の一部をなしていることが示されました。

$c_{ij}$が$ab$を法とする既約剰余類を網羅していること

$c_{ij}$が$ab$を法とする既約剰余類を網羅していることを示すためには，$ab$と互いに素である整数$c$に対し，必ず

を満たすことを示せばよいです。$ab$と互いに素である整数$c$は$a$および$b$とも互いに素であることから，既約剰余類の定義より

\begin{cases}
c\equiv a_{i}\pmod{a}\\[0.7em]
c\equiv b_{i}\pmod{b}
\end{cases}

となる$i,j$がただ一つ存在します。これより，$x{=}c$は連立方程式($\ref{連立方程式}$)の解となることが分かりました。一方，$c_{ij}$は中国剰余定理より連立方程式($\ref{連立方程式}$)のただ一つの解であるため，式($\ref{パート3の主題}$)が示されました。