【徹底解説】一次合同式の解の公式

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

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

目次

一次合同式の解の公式

自然数$n$と整数$a,b$に対し,$\gcd(a,n){=}1$ならば,一次合同式

\begin{align}
ax\equiv b\pmod{n}\label{主題1}
\end{align}

は$n$を法としてただ一つの解をもち,それは

\begin{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}

が成り立ちます。

シェアはこちらからお願いします!

コメント

コメントする

※ Please enter your comments in Japanese to distinguish from spam.

目次