センター試験の問題から - ノリの悪い日記

$2022$ 年のセンター試験の問題をやってみる.

【問】

$11^5x - 2^5y = 1$ の整数解のうち, $x$ が正の整数で最小のものを求めよ.

【解】

ほとんど,こけおどしだが, 時間がない中で計算ミスは避けたい.

$11^5x \equiv 1 \pmod{32}$

を解くだけだが, さすがに $x$ の前の係数が大きいので, 簡単にする必要がある.

まず, $32$ の倍数のテーブルを作ってからやった方がミスが少ないと思う ( $5$ 倍ぐらいまででよかったかもしれない).

$32 \times 1 = 32$
$32 \times 2 = 32 + 32 = 64$
$32 \times 3 = 32 + 64 = 96$
$32 \times 4 = 64 + 64 = 128$
$32 \times 5 = 32 \times 10 /2 = 160$
$32 \times 6 = 160 + 32 = 192$
$32 \times 7 = 320 - 96 = 224$
$32 \times 8 = 320 - 64 = 256$
$32 \times 9= 320 - 32= 288$

それで, 法を $32$ として,

$\begin{eqnarray} 11^5 &\equiv& 121^2\times11 \\ &\equiv& (-7)^2\times11 \\ &\equiv& 49 \times11 \\ &\equiv& 17 \times11 \\ &\equiv& 187 \\ &\equiv& 27 \\ &\equiv& -5 \end{eqnarray}$

後は,

$5x \equiv -1 \pmod{32}$

を解けばよい. これくらい簡単になっていると, 互除法を使わなくとも右辺を $5$ の倍数にどうすればできるか考えればすぐ解ける.

$\begin{eqnarray} 5x &\equiv& -1 + 3 \times 32 \pmod{32}\\ &\equiv& 95 \pmod{32} \end{eqnarray}$

割算は法の値と $x$ の前の係数が互いに素であればできるので,

$x \equiv 19 \pmod{32}$

したがって, 正の整数で最小のものは,

$x = 19$

である. //

※ 二つ前の記事でやったように, カーマイケルの定理を使うと,

$11^8 \equiv 1 \pmod{2^5}$

だとわかるので,

$\begin{eqnarray} 11^5x &\equiv& 1 \pmod{2^5}\\ &\equiv& 11^8 \pmod{2^5} \end{eqnarray}$

したがって,

$\begin{eqnarray} x &\equiv& 1 1^3 \pmod{2^5}\\ &\equiv& -77 \pmod{2^5} \\ &\equiv& -13 \pmod{2^5} \\ &\equiv& 19 \pmod{2^5} \end{eqnarray}$

である. //

※ 実際の問題を見ると $x = 19$ のときの $y$ の値も求めよとある. 計算練習としてやっておく. しばしばあてにならない九去法の検算ではあっている. しかし, こんな計算, 制限時間のある共通テストでよく出すなあ.

$2^5y= 11^5\cdot 19 -1$

$\begin{eqnarray} 11^4 &=& (120+1)^2\\ &=& 14400 + 240 + 1\\ &=& 14641\\ \end{eqnarray}$

$11^5= 146410+ 14641= 161051$

あるいは二項展開して,

$(10+1)^5 \\= 10^5 + 5\cdot10^4+ 10\cdot10^3 \\\quad + 10\cdot10^2 + 5\cdot10 +1 \\=10^5 + 6\cdot10^4+ 10^3 + 5\cdot10 +1 \\= 161051$

としてもよい. いずれにしても,

$161051\cdot19 \\=161051(20-1) \\= 3221020 - 161051 \\=3060000 -31$

したがって,

$32y= 3060000 -32$
$\begin{eqnarray} y &=& 382500\div 4-1\\ &=& 95625 -1 \\ &=& 95624 \end{eqnarray}$

一応求まったが, $11^3 = (120+1)(10+1) = 1331$ を使って, 別の方法で計算してみる. 問題をよく読んで出題者がわかってくれよと必死に (舌足らずに) お願いして (誘導して) いることを推察してみると——特に, 「 $11^4$ を $2^4$ で割った余りは $1$ に等しい」とわざわざ断っている——多分こういうことなのかもしれない. つまり, $2y$ は,

$11^4(11 \cdot 19) - 2^4 (2y) = 1$

の不定方程式を満たしているということを計算のヒントにしろということである ( $11 \cdot 19$ は $2^4$ の倍数に $1$ を足した数である). いわれてみれば成る程で, この場合はこういう処理をするのがキリがよい. 計算のコツはなるべくキリよくすることだなあ.

$\begin{eqnarray} 2^4(2y) &=& 11^5\cdot 19 -1\\ &=& 11^4\cdot 209 -1\\ &=& 11^4 (208+1) -1\\ &=& 11^4\cdot 208 + 122 \cdot 120\\ \end{eqnarray}$

両辺を $2^4=16$ で割って, 同じように考えれば, $11^3$ は明らかに $2$ で割って $1$ 余るから,

$\begin{eqnarray} 2y &=& 11^4\cdot 13 + 915\\ &=& 11^3\cdot 143 + 915\\ &=& 11^3 (142+1) + 915\\ &=& 11^3\cdot 142+ 1331+ 915\\ &=& 11^3\cdot 142+ 2246\\ \end{eqnarray}$

両辺を $2$ で割って,

$\begin{eqnarray} y &=& 11^3\cdot 71 + 1123\\ &=& 1331 \cdot 70 + 1331 + 1123\\ &=& 93170 + 2454\\ &=& 95624\\ \end{eqnarray}$

さらに, もうひとつやってみる.

$\begin{eqnarray} 11^4 &=& (120+1)^2\\ &=& 14400 + 240 + 1\\ &=& 14640 + 1\\ \end{eqnarray}$

で, $209$ は $16$ で割ると $1$ 余るから,

$\begin{eqnarray} 2^4(2y) &=& 11^5\cdot 19 -1\\ &=& 11^4\cdot 209 -1\\ &=& 209(14640 +1) -1\\ &=& 209 \cdot 14640 + 208\\ \end{eqnarray}$

両辺を $2^4=16$ で割って,

$\begin{eqnarray} 2y &=& 209\cdot 915 + 13\\ &=& 209\cdot (914+1) + 13\\ &=& 209\cdot 914+ 222\\ \end{eqnarray}$

両辺を $2$ で割って,

$\begin{eqnarray} y &=& 209\cdot 457 + 111\\ &=& 200 \cdot 457 + 4570 - 457 +111\\ &=& 91400+ 4570 - 346\\ &=& 91400 + 4224\\ &=& 95624\\ \end{eqnarray}$
//