本記事は数学の徹底解説シリーズに含まれます。
初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。
目次
一次合同式の解の公式
自然数$n$と整数$a,b$に対し，$\gcd(a,n){=}1$ならば，一次合同式
\begin{align}
ax\equiv b\pmod{n}\label{主題1}
\end{align}
ax\equiv b\pmod{n}\label{主題1}
\end{align}
は$n$を法としてただ一つの解をもち，それは
\begin{align}
x &= a^{\varphi(n)-1}b\label{主題2}
\end{align}
x &= a^{\varphi(n)-1}b\label{主題2}
\end{align}
で与えられる。
証明
$x$の存在性
一次合同式の解の存在より，式($\ref{主題1}$)を満たす$x$は$n$を法としてただ一つ存在します。
$x$が式($\ref{主題1}$)の解であること
式($\ref{主題2}$)を式($\ref{主題1}$)に代入すると，オイラーの定理より
\begin{align}
ax
= a\cdot a^{\varphi(n)-1}b
= a^{\varphi(n)}b
\equiv b\pmod{n}
\end{align}
ax
= a\cdot a^{\varphi(n)-1}b
= a^{\varphi(n)}b
\equiv b\pmod{n}
\end{align}
が成り立ちます。
コメント