この記事では、次の問題を考察します。
$ n $を正の整数とする。整数$ x, y $に関する方程式$ 5^n x - 2^n y = 1 $を解け。
$ n > 0 $ならば$ \mathrm{gcd}(5^n, 2^n) = 1 $であり、また$ x = 0 $と$ y = 0 $が解になりえないことに注意すると、$ 0 < x < 2^n, 0 < y < 5^n $の範囲に唯一解が存在し、これを求めれば他の解も自動的に求まることが分かります。
そのため、以下ではこの範囲の解を「最小解」と呼び、これについて考察することにします。
さて、これを解くためにはどのような方法が使えるでしょうか。ここでは、最小解が$ 0 < x < 2^n $の範囲にあることを用いて、こんな方法を考えてみましょう。
\begin{eqnarray*} 5^n x - 2^n y \equiv& 1 (\mathrm{mod}\text{ }2^n) \\ 5^n x \equiv& 1 (\mathrm{mod}\text{ }2^n) \\ x \equiv& \frac{1}{5^n} (\mathrm{mod}\text{ }2^n) \\ \end{eqnarray*}
すなわち、$ \mathrm{mod}\text{ }2^n $における$ 5^n $の乗法的逆元を求めればよいことが分かります。都合の良いことに、このような逆元は$ n $にかかわらず存在し、これが最小解を与える$ x $となります。
さて、ということは
$$ \frac{1}{5^1} \mathrm{mod}\text{ }2^1, \frac{1}{5^2} \mathrm{mod}\text{ }2^2,\frac{1}{5^3} \mathrm{mod}\text{ }2^3, \cdots $$
を求めればよいですね。ですが、このままでは$ \mathrm{mod} $が無限にあって面倒ですね。できることなら、$ \mathrm{mod}\text{ }2^1, \mathrm{mod}\text{ }2^2, \mathrm{mod}\text{ }2^3, \cdots $を全て包括したいわば$ \mathrm{mod}\text{ }2^{\infty} $のようなものがあってくれるとよいのですが。
そんな数体系・・・ありますね。そう、$ p $進数です。
実数の$ p $進法による表記とは異なることに注意してください。
実数の小数表記は小数点の右に数字が続きますが、逆に小数点の左に$ 0 $以上$ p $未満の数字が続くものが$ p $進数です。わかりやすいように、$ p = 10 $としていくつか例をあげます。
1番目の例は左に$ 0 $が無限に続いているケースで、この場合は正の整数と一致します。想像通り、この数は整数の$ 6 $を表します。
2番目の例では全ての桁が$ 9 $です。普通の整数の筆算と同じような方法でこれに$ 1 $を足すと、無限に繰り上がって全ての桁が$ 0 $になるので、この数は$ -1 $を表します。
3番目の例では2桁が循環しています。少し計算すると、この数が有理数の$ - \frac{4}{33} $に等しいことが分かります。
4番目の例では左に不規則な数字が無限に続きます。実数には対応するものが存在しない、$ 10 $進数特有の数です。
5番目の例では小数点以下にも桁があります。$ p $進数は一般に、小数点以下に有限個の数字を並べることが許されています。一方、実数とは異なり、小数点以下に無限個の数字を並べることはできません。
$ p $が素数のときは、$ p $進数の振る舞いが良くなり、小数点以下に数のない$ p $進数($ p $進整数と呼ぶことにします)だけで加減乗除が閉じるという性質を持ちます。
例えば、$ p = 3 $のときの次の式を考えましょう。
$$ \cdots 111112 \cdot 2 = \cdots 000001 $$
この末尾から同じ数の桁を取り出すことで、$ \mathrm{mod} $の等式が得られます。
\begin{eqnarray*} (3^0 \cdot 2) \cdot 2 &\equiv 1 (\mathrm{mod}\text{ }3^1) \\ (3^1 \cdot 1 + 3^0 \cdot 2) \cdot 2 &\equiv 1 (\mathrm{mod}\text{ }3^2) \\ (3^2 \cdot 1 + 3^1 \cdot 1 + 3^0 \cdot 2) \cdot 2 &\equiv 1 (\mathrm{mod}\text{ }3^3) \\ (3^3 \cdot 1 + 3^2 \cdot 1 + 3^1 \cdot 1 + 3^0 \cdot 2) \cdot 2 &\equiv 1 (\mathrm{mod}\text{ }3^4) \\ \vdots \end{eqnarray*}
元の問題に使えそうですね。
$ 2 $進数で$ 1 $を$ 5 $で割っていけば、最小解の$ x $が求められます。また同様に、$ 5 $進数で$ -1 $を$ 2 $で割っていけば、最小解の$ y $が求められます。
せっかくなので、$ n = 10 $まで求めましょう。
$ \mathbb{Z}_2 $は$ 2 $進数、$ \mathbb{Z}_5 $は$ 5 $進数を表します。
| $ n $ | $ \frac{1}{5^n} \in \mathbb{Z}_2 $ | $ -\frac{1}{2^n} \in \mathbb{Z}_5 $ | $ x $ | $ y $ |
|---|---|---|---|---|
| $ 1 $ | $ \cdots 0011001101 $ | $ \cdots 2222222222$ | $ 1 $ | $ 2 $ |
| $ 2 $ | $ \cdots 0000101001 $ | $ \cdots 1111111111$ | $ 2 $ | $ 6 $ |
| $ 3 $ | $ \cdots 0011010101 $ | $ \cdots 0303030303$ | $ 5 $ | $ 78 $ |
| $ 4 $ | $ \cdots 1010010001 $ | $ \cdots 0401240124$ | $ 1 $ | $ 39 $ |
| $ 5 $ | $ \cdots 1000011101 $ | $ \cdots 1200342312$ | $ 29 $ | $ 2832 $ |
| $ 6 $ | $ \cdots 0100111001 $ | $ \cdots 0322421131$ | $ 57 $ | $ 13916 $ |
| $ 7 $ | $ \cdots 1010100101 $ | $ \cdots 2411210313$ | $ 37 $ | $ 22583 $ |
| $ 8 $ | $ \cdots 1000100001 $ | $ \cdots 1203102404$ | $ 33 $ | $ 50354 $ |
| $ 9 $ | $ \cdots 0001101101 $ | $ \cdots 3101301202$ | $ 109 $ | $ 415802 $ |
| $ 10 $ | $ \cdots 1101001001 $ | $ \cdots 4023123101$ | $ 841 $ | $ 8020401 $ |
2022年大学入学共通テストでは、$ n = 5 $のときに$ x $が$ 3 $桁であるような解のうち最小のものを求める問題が出題されました。
注: ②は$ n = 5 $のときの式である。
注: (2)では$ 625^2 \equiv 1 (\mathrm{mod}\text{ }2^5) $が示唆されている。
注: []で囲った部分は実際には四角囲みである。
(数学Ⅰ・数学A第4問問題文より引用 ここから)
$ x, y $を②の整数解とする。$ 5^5 x $は$ 5^5 $の倍数であり，$ 2^5 $で割ったときの余りは$ 1 $となる。よって，(2)により，$ 5^5 x - 625^2 $は$ 5^5 $でも$ 2^5 $でも割り切れる。$ 5^5 $と$ 2^5 $は互いに素なので，$ 5^5 x - 625^2 $は$ 5^5 \cdot 2^5 $の倍数である。
このことから，②の整数解のうち$ x $が$ 3 $桁の整数で最小になるのは
$$ x = [\text{サシス}], y = [\text{セソタチツ}] $$
であることがわかる。
(数学Ⅰ・数学A第4問問題文より引用 ここまで)
最初にこの問題を見たとき、「このことから」が非常に非自明であると感じました。しかし、$ p $進数によるアプローチがある今、行間を埋めることができます。
$ x' $を$ 2 $進数における$ 5^5 $の逆数とする。このとき、$ 5^5 x' - 625^2 $の末尾$ 5 $桁は$ 00000 $である。$ 5^5 x - 625^2 \equiv 0 (\mathrm{mod}\text{ }2^5) $は$ 0 \leq x < 2^5 $に唯一解を持つので、それは$ x' $の最後の$ 5 $桁を整数の$ 2 $進表記とみたものと等しい。
ここで、$ 625^2 = 5^8 \equiv 1 (\mathrm{mod}\text{ }2^5) $であるから、
$$ 5^{-5} \equiv 5^{-5} \cdot 5^8 = 5^3 = 125 (\mathrm{mod}\text{ }2^5) $$
が成り立つ。よって、$ 125 - 32 < 10^2$であるから、②の整数解のうち$ x $が$ 3 $桁の整数で最小になるのは$ 125 $である。
この後の問題では、$ 11^5 x - 2^5 y = 1 $の整数解について考察しています。これに関しても、$ 2 $進法で$ 11^5 $の逆数を考えることで解くことができます。