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

最近の文部科学省の調査により、いよいよ大学入試の差別問題の深刻さが浮き彫りになってきました。教育界全体が差別撲滅に取り組むのは当然のこととして、差別の現場が果たして入学試験だけなのか否か、実態調査を急ぐべきでしょう。


今回の創作整数問題は47問目です。原子番号47と言えば銀(Ag)ですが、電気伝導率が最高の元素であることが知られています(逆に言えば電気抵抗率が最低ということになります)。電線には銅が使われていますが、これをすべて銀に替えると日本では年間で約400万kWhの省電力が可能です。これは原子力発電所2~3基分の年間発電量に相当しますが、全電線を銀線に替えるコストを考えると全く現実的ではありませんね・・・(笑)。


創作整数問題#47


《問題#47》

$\displaystyle \sum^{1111}_{k=1} {1111}^{k}$を$11111$で割ったときの余りを求めよ。

(創作問題)


$1$しか登場しない問題です・・・。

 

 

 

» 答えはこちら

答えは $\color{red}{1111}$ で、やはり$1$しか登場しません(笑)。

» 閉じる


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


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

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

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

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

$37$の倍数判定法なんぞ使う場面はまず無いでしょうが、題材としては面白いのではないかと思い、問題風にアレンジしてみました。

一般に倍数判定法というのは、単純に割り算して割り切れるかどうかを確かめるのではなく、より少ない手数で可約性を判断できるような方法のことを指しています。例で示した$3$の倍数判定法は、ある整数$N$の剰余をそれよりも小さい$N$の各位の数の総和の剰余にすり替えて、計算量を大きく減らすことができる画期的な方法です。これと同じように、マジメに計算するよりも少ない労力で$37$の倍数判定ができるような方法を編み出そう、というのが本問の趣旨です。

●   ●   ●

(1)の解説

まず$1000$を$37$で割った余りを求めてみると、余りは$1$となります。つまり、$$1000 \equiv 1 \pmod{37}$$が成立しますので、この両辺を$n$乗すれば$$1000^n \equiv 1^n\ (=1) \pmod{37}$$という関係式を得ることができます。

したがって$n$を正の整数とするとき、$1000^n$を$37$で割った余りは常に$1$となることが示されました。

●   ●   ●

(2)の解説

(1)より、$1000$を$37$で割った余りは$1$となることが分かったので、ある整数$N$が$37$の倍数かどうかを判定するには、$N$を下$3$桁から順に$3$桁ずつ区切っていき、区切られた$3$桁もしくは$3$桁未満の数をすべて加えて得られる数$N’$が$37$で割り切れるかどうかを調べればよい、ということになります。

言葉だけだと少し分かりにくいので、具体例で見てみましょう。

例として$1234567$が$37$の倍数かどうかを判定してみます。$1234567$を下$3$桁から順に$3$桁ずつ区切ると

$1$、$234$、$567$

となります。これらの和は$$1+234+567=802$$なので、$1234567$を$37$で割った余りは$802$を$37$で割った余りに等しいことになります($N$を$1234567$とすると、$N’$が$802$に相当します)。ここで$802$は$37$で割り切れないので、$1234567$は$37$の倍数でないことが分かります。実際、$1234567$も$802$も$37$で割った余りはともに$25$となり一致しています。

次に$123456789$が$37$の倍数かどうかを判定してみます。$123456789$を下$3$桁から順に$3$桁ずつ区切ると

$123$、$456$、$789$

となります。これらの和は$$123+456+789=1368$$なので、$123456789$を$37$で割った余りは$1368$を$37$で割った余りに等しいことになります。このまま余りを求めても良いのですが、$1368$は$4$桁の数なのでさらに判定法が適用できて、$$1+368=369$$の余りを調べればよいことになります。$369$は$37$で割り切れないので、$123456789$は$37$の倍数でないことが分かります。実際、$123456789$も$369$も$37$で割った余りはともに$36$なので、これも一致しています。

●   ●   ●

このようにして(1)の結果を利用した判定法を用いることで、判定したい自然数$N$がどんなに大きくても、結局は$3$桁の自然数の余りに帰着できるのです。

それでは $N=486652173126598$ の場合について、$37$の倍数判定法を用いて調べてみましょう。この数を下$3$桁から順に$3$桁ずつ区切っていくと、

$486$、$652$、$173$、$126$、$598$

となります。これらの和は$2035$となり、これに対してさらに判定法を適用すると、$2+35=37$ となるので、これは$37$で割り切れます。

したがって $N=486652173126598$ は$37$の倍数であることが分かりました。


(コメント)

本問のネタは$$1000 \equiv 1 \pmod{37}$$という関係式に尽きます。これをもとにして倍数判定法を導くというもので、なかなか類のない出題だったのではないでしょうか?

この他にも$$100 \equiv 1 \pmod{11}$$や$$1000 \equiv 1 \pmod{27}$$といった関係式から、本問と同様に倍数判定法が導出できそうです。


倍数判定法でよく知られているのは$3$、$9$などでしょうか。$2$や$4$、$5$の倍数判定は非常に簡単なので、高校入試の問題にすらなかなか採用されません。

皆さんのお気に入りの倍数判定法があれば是非コメント欄にてご紹介下さい!

 

コメントを残す

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