本記事では，数学検定1級で頻出のトピックについてまとめていきます。
初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。
目次
平方剰余と法の累乗
次の合同式を解け。
\begin{align}
x^{2} &\equiv 11\pmod{125}
\end{align}
x^{2} &\equiv 11\pmod{125}
\end{align}
方針
$p^{e}$を法とする合同式は$p$を法とする合同式から順に考えていきます。
解説
法の$125$は$5^{3}$であるから，$5$が法である場合から考えます。
\begin{align}
x^{2} &\equiv 11\pmod{5}\label{1}
\end{align}
x^{2} &\equiv 11\pmod{5}\label{1}
\end{align}
一つの解は$x=4$であるから，式($\ref{1}$)の解は自然数$y$を用いて
\begin{align}
x &= \pm(4 + 5y)\label{xをyで表す}
\end{align}
x &= \pm(4 + 5y)\label{xをyで表す}
\end{align}
と表されます。まず正の解だけを考えます。式($\ref{xをyで表す}$)を式($\ref{1}$)に代入して法を$5^{2}$とすると，
\begin{alignat}{2}
(4+5y)^{2} &\equiv 11&&\pmod{5^{2}}\\[0.7em]
40y &\equiv -5&&\pmod{5^{2}}\\[0.7em]
8y &\equiv -1&&\pmod{5}\label{yの合同式}
\end{alignat}
(4+5y)^{2} &\equiv 11&&\pmod{5^{2}}\\[0.7em]
40y &\equiv -5&&\pmod{5^{2}}\\[0.7em]
8y &\equiv -1&&\pmod{5}\label{yの合同式}
\end{alignat}
が得られます。一つの解は$y=3$であるから，式($\ref{yの合同式}$)の解は自然数$z$を用いて
\begin{align}
y &= 3 + 5z\label{yをzで表す}
\end{align}
y &= 3 + 5z\label{yをzで表す}
\end{align}
と表されます。式($\ref{yをzで表す}$)を式($\ref{xをyで表す}$)に代入すると，
\begin{align}
x &= 4 + 5(3+5z) = 19 + 5^{2}z\label{xをzで表す}
\end{align}
x &= 4 + 5(3+5z) = 19 + 5^{2}z\label{xをzで表す}
\end{align}
と表されます。式($\ref{xをzで表す}$)を式($\ref{1}$)に代入して法を$5^{3}$とすると，
\begin{alignat}{2}
(19 + 5^{2}z)^{2} &\equiv 11&&\pmod{5^{3}}\\[0.7em]
38\cdot 5^{2}z &\equiv -350&&\pmod{5^{3}}\\[0.7em]
38z &\equiv -14&&\pmod{5}\\[0.7em]
38z &\equiv 1&&\pmod{5}\label{引き算1}
\end{alignat}
(19 + 5^{2}z)^{2} &\equiv 11&&\pmod{5^{3}}\\[0.7em]
38\cdot 5^{2}z &\equiv -350&&\pmod{5^{3}}\\[0.7em]
38z &\equiv -14&&\pmod{5}\\[0.7em]
38z &\equiv 1&&\pmod{5}\label{引き算1}
\end{alignat}
が得られます。一方で，$5$を法として
\begin{align}
40z &\equiv 0\pmod{5}\label{引き算2}
\end{align}
40z &\equiv 0\pmod{5}\label{引き算2}
\end{align}
となるため，式($\ref{引き算2}$)から式($\ref{引き算1}$)を引くと，
\begin{align}
2z &\equiv 4\pmod{5}
\end{align}
2z &\equiv 4\pmod{5}
\end{align}
が得られます。一つの解は$z=2$であるから，式($\ref{xをzで表す}$)は
\begin{align}
x &= 4 + 5(3+5z) = 19 + 5^{2}\cdot 2 = 69
\end{align}
x &= 4 + 5(3+5z) = 19 + 5^{2}\cdot 2 = 69
\end{align}
となります。冒頭で$x$は正の解だけを考えていたことに注意すると，求める解は
\begin{align}
x \equiv \pm 69\pmod{5^{3}}
\end{align}
x \equiv \pm 69\pmod{5^{3}}
\end{align}
となります。
いずれのフェーズでも，合同式の両辺を$5$の冪乗で割ることにより$5$を法とする合同式に帰着させている点がポイントです。
コメント