2
高校数学解説
文献あり

大学入学共通テストにp進数が出ていた話

467
0

序文

この記事では、次の問題を考察します。

nを正の整数とする。整数x,yに関する方程式5nx2ny=1を解け。

n>0ならばgcd(5n,2n)=1であり、またx=0y=0が解になりえないことに注意すると、0<x<2n,0<y<5nの範囲に唯一解が存在し、これを求めれば他の解も自動的に求まることが分かります。

そのため、以下ではこの範囲の解を「最小解」と呼び、これについて考察することにします。

さて、これを解くためにはどのような方法が使えるでしょうか。ここでは、最小解が0<x<2nの範囲にあることを用いて、こんな方法を考えてみましょう。

5nx2ny1(mod 2n)5nx1(mod 2n)x15n(mod 2n)

すなわち、mod 2nにおける5nの乗法的逆元を求めればよいことが分かります。都合の良いことに、このような逆元はnにかかわらず存在し、これが最小解を与えるxとなります。

さて、ということは

151mod 21,152mod 22,153mod 23,

を求めればよいですね。ですが、このままではmodが無限にあって面倒ですね。できることなら、mod 21,mod 22,mod 23,を全て包括したいわばmod 2のようなものがあってくれるとよいのですが。

そんな数体系・・・ありますね。そう、p進数です。

p進数

実数のp進法による表記とは異なることに注意してください。

実数の小数表記は小数点の右に数字が続きますが、逆に小数点の左に0以上p未満の数字が続くものがp進数です。わかりやすいように、p=10としていくつか例をあげます。

  • 000006
  • 999999
  • 121212
  • 390281
  • 000001.5

1番目の例は左に0が無限に続いているケースで、この場合は正の整数と一致します。想像通り、この数は整数の6を表します。

2番目の例では全ての桁が9です。普通の整数の筆算と同じような方法でこれに1を足すと、無限に繰り上がって全ての桁が0になるので、この数は1を表します。

3番目の例では2桁が循環しています。少し計算すると、この数が有理数の433に等しいことが分かります。

4番目の例では左に不規則な数字が無限に続きます。実数には対応するものが存在しない、10進数特有の数です。

5番目の例では小数点以下にも桁があります。p進数は一般に、小数点以下に有限個の数字を並べることが許されています。一方、実数とは異なり、小数点以下に無限個の数字を並べることはできません。

pが素数のとき

pが素数のときは、p進数の振る舞いが良くなり、小数点以下に数のないp進数(p進整数と呼ぶことにします)だけで加減乗除が閉じるという性質を持ちます。

modを内包する

例えば、p=3のときの次の式を考えましょう。

1111122=000001

この末尾から同じ数の桁を取り出すことで、modの等式が得られます。

(302)21(mod 31)(311+302)21(mod 32)(321+311+302)21(mod 33)(331+321+311+302)21(mod 34)

元の問題に使えそうですね。

方針

2進数で15で割っていけば、最小解のxが求められます。また同様に、5進数で12で割っていけば、最小解のyが求められます。

せっかくなので、n=10まで求めましょう。

一覧

Z22進数、Z55進数を表します。

n15nZ212nZ5xy
10011001101222222222212
20000101001111111111126
300110101010303030303578
410100100010401240124139
510000111011200342312292832
6010011100103224211315713916
7101010010124112103133722583
8100010000112031024043350354
900011011013101301202109415802
10110100100140231231018418020401

試験問題

2022年大学入学共通テストでは、n=5のときにx3桁であるような解のうち最小のものを求める問題が出題されました。

注: ②はn=5のときの式である。
注: (2)では62521(mod 25)が示唆されている。
注: []で囲った部分は実際には四角囲みである。

(数学Ⅰ・数学A第4問問題文より引用 ここから)
x,yを②の整数解とする。55x55の倍数であり,25で割ったときの余りは1となる。よって,(2)により,55x625255でも25でも割り切れる。5525は互いに素なので,55x62525525の倍数である。
このことから,②の整数解のうちx3桁の整数で最小になるのは
x=[サシス],y=[セソタチツ]
であることがわかる。
(数学Ⅰ・数学A第4問問題文より引用 ここまで)

最初にこの問題を見たとき、「このことから」が非常に非自明であると感じました。しかし、p進数によるアプローチがある今、行間を埋めることができます。

x2進数における55の逆数とする。このとき、55x6252の末尾5桁は00000である。55x62520(mod 25)0x<25に唯一解を持つので、それはxの最後の5桁を整数の2進表記とみたものと等しい。
ここで、6252=581(mod 25)であるから、
555558=53=125(mod 25)
が成り立つ。よって、12532<102であるから、②の整数解のうちx3桁の整数で最小になるのは125である。

次の問題

この後の問題では、115x25y=1の整数解について考察しています。これに関しても、2進法で115の逆数を考えることで解くことができます。

まとめ


大学入学共通テストにはp進数が出題されたのである!!!
ΩΩΩ<な、なんだってー!?

参考文献

投稿日:2022925
更新日:2024930
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

nayuta_ito
103
34503

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. 序文
  2. $ p $進数
  3. 方針
  4. 一覧
  5. 試験問題
  6. まとめ
  7. 参考文献