【初学者向け】一次合同式の解の存在

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

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

目次

一次合同式の解の存在

自然数$n$と整数$a,b$に対して,一次合同式

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

が整数解をもつための必要十分条件は,$b$が$d{=}\gcd(a,n)$の倍数となることである。ただし,$a\neq 0$とする。

証明

式($\ref{主題}$)を変形すると,整数$y$を用いて

\begin{align}
ax + ny &= b\label{一次不定方程式}
\end{align}

が得られます。一次不定方程式の解の存在より,式($\ref{一次不定方程式}$)が解をもつための必要十分条件は$b$が$d$の倍数となることであるため,題意は示されました。

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

コメント

コメントする

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

目次