創作整数問題#47解法＆創作整数問題#48

久し振りの更新です。師走も中旬となり、冬もいよいよ深まってくる季節となりましたね。今シーズンも早いものでセンター試験まで残り1か月余りとなりました。体調管理に気を付けて過ごしたいですね！

さて、受験界隈は医学部不適切入試の話題で持ちきりです。文部科学省は事態を重く見てか、出願シーズンに差し掛かる前の最終報告を急いだようです（当の文科省は「入試を控える受験生に、長い間不安を与えることになり、大変申し訳なく思っている」と謝罪しているようですが･･･）。

不適切入試と指摘されたのは国立大学では神戸大学、私立大学では東京医科大学、順天堂大学、日本大学、昭和大学、岩手医科大学、金沢医科大学、福岡大学、北里大学、聖マリアンナ医科大学で、合計10大学に上ります。これまで、医学部（特に私立）は浪人生や女子に厳しいというのが通説となっていましたが、今回の件でとうとう根拠の無い噂とは言えなくなりました。

今回の件で追加合格を出すとなると、大学によっては来年の入学定員を削減することになり兼ねず、将来の受験生への影響も危惧されます。受験生としても出願に慎重になるでしょうから、大学の経営は逼迫することが予想されます。元はと言えば、どこぞの官僚の息子を裏口入学させたことで発覚した一連の不適切入試の件ですが、その余波がいつ収束するのかは誰にも読めませんね･･･。

創作整数問題#48

《問題#48》

$48$進法における$5^n$の下2桁が$01$となるような最小の自然数$n$を求めよ。

（創作問題）

48題目ということで、48に因んだ問題にしてみました。「下2桁」というところもちょっとしたアクセントですね！

（ただし$n$は$10$進法でお答えください･･･）

» 答えはこちら

答えは $\color{red}{n=192}$ です。

» 閉じる

創作整数問題#47（解き方）

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

$\displaystyle \sum^{1111}_{k=1} {1111}^{k}$を$1111$で割ったときの余りはもちろん$0$ですが、$11111$は5桁の数です。ここが少し面倒な部分かもしれませんが、計算自体は容易でしょう。こういうタイプの問題では${1111}^{k}$の剰余の周期性を見破ることが重要です。試しに小さい$k$について、$1111^k$の剰余を$\bmod{11111}$ で計算してみましょう。以下、合同式はすべて$\bmod{11111}$ とします。

$\begin{align} 1111^{2} &=1234321 \\ &\equiv 1234321-1111100-111110-11111 \\ &\equiv 1000 \end{align}$

$\begin{align} 1111^{3} &\equiv 1000 \cdot 1111 \\ &=1111000 \\ &\equiv 1111000-1111100 \\ &\equiv -100 \end{align}$

$\begin{align} 1111^{4} &\equiv -100 \cdot 1111 \\ &=-111100 \\ &\equiv -111100+111110 \\ &\equiv 10 \end{align}$

$\begin{align} 1111^{5} &\equiv 10 \cdot 1111 \\ &=11110 \\ &\equiv 11110-11111 \\ &\equiv -1 \end{align}$

$-1$が出てきたのでここで一旦ストップします。これを2乗すれば$1$になるので剰余の周期が$10$ではないかとアタリを付けることができます。
このまま計算し続けても良いですが、せっかく$-1$が出てきたので、これを利用しましょう。

$1111^{5} \equiv -1$ となるので $1+1111^{5}$ は$11111$で割り切れます。よってこれを$\displaystyle \sum^{1111}_{k=1} {1111}^{k}$の中にどんどん作れば計算が非常に簡単になります。例として $1 \leqq k \leqq 10$ の部分でやってみると、$$\begin{align} &\ \ \ \ 1111+1111^2+1111^3+1111^4+1111^5 \\ &\ \ \ \ \ +1111^6+1111^7+1111^8+1111^9+1111^{10} \\ &=(1+1111^5)(1111+1111^2+1111^3+1111^4+1111^5) \\ &\equiv 0 \end{align}$$となるので、${1111}^{k}$は連続する$10$項を単位として、和が$11111$の倍数となっていることが分かります。

したがって$\displaystyle \sum^{1110}_{k=1} {1111}^{k}$は$11111$の倍数なので、$\displaystyle \sum^{1111}_{k=1} {1111}^{k}$を$11111$で割ったときの余りは末項である$1111^{1111}$を$11111$で割ったときの余りに等しいことが分かります。

$1111^{10} \equiv 1$ より、${1111}^{1110}$を$11111$で割ったときの余りは$1$なので、$1111^{1111}$を$11111$で割ったときの余りは$1111$となります。

以上より、$\displaystyle \sum^{1111}_{k=1} {1111}^{k}$を$11111$で割ったときの余りは$$\color{red}{1111}$$と求められます。

（コメント）

一見すると面倒そうではありますが、いざ計算するとそれほど込み入った話ではありません。

因みに、$11111$のように同じ数字のみから成る数を「レピュニット数」と言います。レピュニット数には面白い性質が沢山あるのですが、その紹介はまたの機会に･･･。

（別解を頂きました）

コメント欄にて、当サイトがいつもお世話になっているたけちゃんさんから別解をご提供頂きました！

$\bmod{11111}$ によると、$1111 \equiv -10000$ であり、$1111^2 \equiv 10^8$ となるので、$$\begin{align} & \ \ \ \ \ 1+1111^2+1111^4+1111^6+1111^8 \\ & \equiv 100000001000000010000000100000001 \end{align}$$が成り立ちます。

ここで創作整数問題#46で紹介した要領で$11111$の倍数判定法を用います。$99999$は$11111$の倍数なので、$$\begin{align} 100000 &= 99999+1 \\ & \equiv 1 \end{align}$$です。これより、ある数$N$が$11111$の倍数かどうかを判定するには$N$を$5$桁ごとに区切ってできる数の和を調べればよいことになります。

先ほどの$33$桁の数を$5$桁ごとに区切ると、$$100|00000|10000|00010|00000|01000|00001$$となるので、$$\begin{align} & \ \ \ \ \ 1+1111^2+1111^4+1111^6+1111^8 \\ & \equiv 100000001000000010000000100000001 \\ & \equiv 100+0+10000+10+0+1000+1 \\ &=11111 \\ & \equiv 0 \end{align}$$となります。したがって $1+1111^2+1111^4+1111^6+1111^8$ は$11111$の倍数であることが分かり、奇数乗の和についても$$\begin{align} &\ \ \ \ \ 1111+1111^3+1111^5+1111^7+1111^9 \\ &= 1111(1+1111^2+1111^4+1111^6+1111^8) \\ & \equiv 1111\cdot0 \pmod{11111} \end{align}$$となり、同様に$11111$の倍数であることが分かります。これより等比数列$\{1111^k\}$の連続する$10$項の和は$11111$の倍数なので、$\displaystyle \sum^{1111}_{k=1} {1111}^{k}$を$11111$で割ったときの余りは初項の$1111$に等しいことが分かります。

解答例の方法でも計算はそれほど複雑ではありませんが、こちらの別解では更に計算を省力化できます。$1111 \equiv -10000$ という関係に着目した上手い解法ですね！

(2019/04/07追記)

2018年の第28回日本数学オリンピック予選の第4問にて、

「${1111}^{2018}$を$11111$で割った余りを求めよ」

という出題がありました。