【数検1級対策】平方剰余と法の累乗

本記事では,数学検定1級で頻出のトピックについてまとめていきます。

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

目次

平方剰余と法の累乗

次の合同式を解け。

\begin{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=4$であるから,式($\ref{1}$)の解は自然数$y$を用いて

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

が得られます。一つの解は$y=3$であるから,式($\ref{yの合同式}$)の解は自然数$z$を用いて

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

と表されます。式($\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}

が得られます。一方で,$5$を法として

\begin{align}
40z &\equiv 0\pmod{5}\label{引き算2}
\end{align}

となるため,式($\ref{引き算2}$)から式($\ref{引き算1}$)を引くと,

\begin{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$は正の解だけを考えていたことに注意すると,求める解は

\begin{align}
x \equiv \pm 69\pmod{5^{3}}
\end{align}

となります。

いずれのフェーズでも,合同式の両辺を$5$の冪乗で割ることにより$5$を法とする合同式に帰着させている点がポイントです。

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

コメント

コメントする

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

目次