創作整数問題#45解法&創作整数問題#46

先日はお月様が綺麗に見えましたね。日本では旧暦8月の十五夜の月を「中秋の名月」と呼びますが、英語圏にも”Harvest Moon”という似た呼び名があります。ただし正確には両者は必ずしも一致しません。

中秋の名月とは「十五夜に見える月」の意味で、必ずしも満月とは限りません。それに対して”Harvest Moon”は「秋分に最も近い満月」を指します。ちょうどこの辺りの時期に実りの季節を迎えることから”Harvest”の名が付いたようです。

呼び名はさておき、月を愛でる風流心は万国共通なのでしょうね。


創作整数問題#46


《問題#46》

ある整数Nが整数kの倍数であるかどうかを簡便に判別する数学的な方法は「kの倍数判定法」と呼ばれる。例えば、3の倍数判定法として、「整数Nの各位の数の総和が3の倍数ならばN3の倍数である」というものが知られている。

以上のことを踏まえて37の倍数判定法を導いてみよう。

(1)nを正の整数とするとき、1000n37で割った余りを求めよ。

(2)(1)の結果を利用して37の倍数判定法を提案せよ。また、それを用いて N=48665217312659837の倍数かどうかを判定せよ。

(創作問題)


いわゆる倍数判定法に関する問題です。37の倍数判定が必要になる場面はなかなか想定しにくいですが・・・(笑)

 

 

 

» 答えはこちら

(1)答えは \colorred1 です。

(2)ある整数N37の倍数であるかどうかを判別するには、Nを下3桁から順に3桁ずつ区切っていき、区切られた3桁もしくは3桁未満の数をすべて加えて得られる数N37で割り切れるかどうかを調べればよい。

» 閉じる


創作整数問題#45(解き方)



よくあるタイプの問題ですが、アプローチが思い付かないとなかなか攻略が難しい種類の問題です。素数絡みの整数問題では、まず初めに剰余や素因数の個数などについて絞り込めないかを考えましょう。特に、因数分解が難しい(または不可能な)問題では剰余による絞り込みが有効なことが多いです。

本問もまさにそのタイプの問題で、偶奇関係から絞り込むことができます。(1)と(2)のいずれの方程式も二乗の項から成るので、この場合は4を法とした剰余類を考えるとよいでしょう。

まず、平方数について一般に、

nが偶数 n24m 型の整数

nが奇数 n24m+1 型の整数

が言えることを確認しておきましょう。他に役立つ法としては358などが挙げられます。

●   ●   ●

(1)の解説

ここではまず右辺d2について場合分けしましょう。

偶奇から絞り込んでもよいのですが、偶数であるような素数は2しかないので、d=2 のとき、およびdが奇素数のときを調べればよいことになります。

dが偶数、即ち d=2 のとき、右辺は4となりますが、a2+b2+c2=4を満たすような素数abcの組は存在しません。したがってdが与方程式を満たすならば、それは奇素数のときに限ります。

このとき mod4 で考えると、a2+b2+c21(mod4)となります。先程の説明の通り、平方数は mod4 において0または1しか取り得ないため、この等式を満たすためにはabcのうち2つが偶数、残りの1つが奇数である必要があります。abcは対称であるため、これより一般性を失うことなく a=b=2 と置けます。このとき方程式は22+22+c2=d2 c2d2=8 (cd)(c+d)=8と変形でき、cd<c+d より、{cd=1c+d=8または{cd=2c+d=4に限られます。しかしこれを満たすような素数cdは存在しないので、結局、方程式a2+b2+c2=d2を満たすような素数abcdは存在しません。

●   ●   ●

(2)の解説

こちらもまずは偶奇で絞り込みます。

dが偶数、即ち d=2 のとき、右辺は8となりますが、a2+b2+c2=8を満たすような素数abcの組は存在しないので、dは奇素数に限ります。

(1)と同様に mod4 で考えると、a2+b2+c22(mod4)となります。平方数が mod4 において取り得る値を考えると、abcのうち1つが偶数で残りの2つが奇数となることが必要です。abcは対称なので、一般性を失うことなく abc と置けます。これより、a=2 が決まります。

このとき方程式は(★)b2+c2=2d24となります。

ここで d=3 とすると()式はb2+c2=14となりますが、これを満たすような素数bcは存在しません。したがって素数d3ではなく、また、偶数でも3の倍数でもないので、正の整数kを用いてd=6k±1と置くことができます。これよりd21(mod6)となるので、mod6 で考えると()式はb2+c224(mod6)となります。これは mod3 だとb2+c21(mod3)となるので、bcのうち一方のみが3の倍数となることが言えます(※平方数は mod3 において0または1しか取り得ません)。3の倍数であるような素数は3しかないので、b=3 と決まります。

これにより、()式は(♪)c2=2d213となります。

()式を満たす素数の組cdが存在しないことを示すため、ここでは mod8 の力を借りましょう。mod8 において、平方数のとり得る値は014のみです。したがって()式を mod8 で考えると、左辺のとり得る値は014のみであり、右辺のとり得る値は35のみとなるので、共通する値が存在せず不合理です。

以上より、方程式a2+b2+c2=2d2を満たすような素数abcdの組は存在しないことが示されました。


(コメント)

平方数の和が登場する整数問題は剰余類と絡めて出題されることが多いです。こうした問題を解答する際は、絞り込みに平方剰余の知識が活きてくる場面も多々ありますので、これを機にマスターしておきたいですね。なお、当サイトの「整数第3章第1節B問題」に剰余や冪に関する整数問題を掲載していますので、演習用に是非ご利用下さい。

今回の(2)は誘導設問がほとんど無いので難度は高めだったかもしれませんが、その辺の数学コンテストよりは易しいと思います・・・(多分)。やはり mod で上手く絞り込めたときは爽快ですね(笑)。


 

 

“創作整数問題#45解法&創作整数問題#46” への1件の返信

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

©Copyright 2017-2025 理系のための備忘録 All Rights Reserved.