【挑戦】(数セミ)エレガントな解答をもとむを解く㉕

本記事の内容
問題を明示します。
チャレンジの結果は…？
筆者の解答を紹介します。
投稿されたエレガントな解答を紹介します！
読者の皆様への挑戦状！ぜひ解いてみて下さい！
結

本記事の内容

本記事は『数学セミナー』(日本評論社)に掲載されている”エレガントな解答をもとむ”に出題されいている問題を1時間で解けるか、という挑戦をする記事です。

本記事を読むにあたり、前提知識は基本的に必要ありませんが、以前紹介した記事の内容を使う場合はその旨を記述することにします。

今回も「エレガントな解答をもとむ selections」に掲載されいている問題です。

前回の問題については以下の記事を御覧ください！

【挑戦】(数セミ)エレガントな解答をもとむを解く㉔

...

問題を明示します。

$10$と互いに素な全ての自然数は、$11\cdots1$のように、$1$を並べた倍数を必ず持つことを示してください。
例　$3\times37=111$
　　$7\times15873=111111$
　　$9\times12345679=1111111111$
　　$11\times1=11$
　　$13\times8547=111111$　
数学セミナー編集部編（2001）『エレガントな解答をもとむ selections』日本評論社 p21.

チャレンジの結果は…？

チャレンジの結果…解けました！
久しぶりの整数問題でしたが、なんとか解けました。
問題文はシンプルですが、今回は1時間目一杯使いました。

筆者の解答を紹介します。

まず、問題文を言い換えてみます。

問題文
$n\in\mathbb{N}$が$\gcd(n,10)=1$を満たすならば、$\exists s,t\in\mathbb{N}\ {\rm s.t.}$ $$ ns=10^t+10^{t-1}+\cdots+10^2+10+1 $$ である。

を証明しなさい、ということです。
こういう場合は筆者の経験上(大した経験ではありませんが)、剰余(あまり)に着目すると解きやすい傾向にあります。

$A_m=111\cdots1$($1$が$m$個並んでいる)とすると、$A_m$は
$$
A_m=\sum_{k=0}^m10^k
$$
と書くことができます。
このとき、$\gcd(n,10)=1$、すなわち$n$と互いに素な自然数$n$に対して、$A_m$を$n$で割った商を$q_m$、余りを$r_m$とすれば、
$$
A_m=nq_m+r_m\quad (0\leq r_m\leq n-1)
$$
と書くことができます。

証明したいことは$r_m=0$なのですが、どう証明したものでしょうか。
少し悩みました。
発想はいくらでもあるのでしょうが、筆者は$\displaystyle\frac{A_m}{n}$をどうにか変形して$10^X\times111\cdots1 $という形にすることで、$\gcd(n,10)=1$から$n|111\cdots1$である、と結論づけると良いのではないか？という発想に至りました。

試行錯誤の末、$n+1$個の$A_m$、すなわち$A_1,A_2,\cdots,A_n,A_{n+1}$を$n$で割ることにしました。
すると、$n$で割ったときの余りは$0,1,\cdots,n-1$の$n$パターンしか存在しません。
したがって、$A_1,\cdots,A_{n+1}$の中には$n$で割ったときに余りが一致するようなペアが少なくとも1つ存在します。
これは抽斗論法(鳩の巣原理とも)というやつです。
抽斗論法については【代数学の基礎シリーズ】群論編その46を御覧ください。

さて、余りが一致するペアをそれぞれ$A_i$、$A_j$とします。
このとき、一般性を失わず$A_i>A_j$としてOKです($A_j>A_i$としても記号の役割が変わるだけ)。
さて、
\begin{eqnarray}
A_i-A_j&=&\sum_{k=0}^i10^k-\sum_{k=0}^j10^k\\
&=&\sum_{k=0}^{i-j-1}10^k\times 10^{j+1}
\end{eqnarray}
となります。
一方で、$A_i$および$A_j$を$n$で割ったとき、その商をそれぞれ$p_i,p_j\in\mathbb{N}$とすると
$$
A_i=np_i+r,\quad A_j=np_j+r
$$
と書けます。
このとき、
$$
A_i-A_j=np_i+r-np_j-r=np_i-np_j=n(p_i-p_j)
$$
となるため、$n|(A_i-A_j)$、すなわち$A_i-A_j$は$n$で割り切れます。
今、
$$
A_i-A_j=\sum_{k=0}^{i-j-1}10^k\times 10^{j+1}
$$
だったわけですので、
$$
n\left|\left(\sum_{k=0}^{i-j-1}10^k\times 10^{j+1}\right)\right.
$$
となります。
すなわち、$n$は$\displaystyle\sum_{k=0}^{i-j-1}10^k$か$10^{j+1}$の少なくとも一方を割り切ります。
しかしながら、$\gcd(n,10)=1$ですので、$n\not|10^{j+1}$です。
故に、
$$
n\left|\sum_{k=0}^{i-j-1}10^k\right.
$$
となります。
$$
\sum_{k=0}^{i-j-1}10^k=111\cdots1
$$
($1$が$i-j-1$個並んでいる)ですから、証明完了です。

投稿されたエレガントな解答を紹介します！

筆者の解答と似ている部分は省略します。

（前略）

全体を通じて$m$は$10$と互いに素な自然数とします。

（中略）

　　さて、この「鳩ノ巣原理」を用いると、次のような事実が証明できます。

　補題「$a$と$x$が互いに素であるとき$a^n-1$が$x$の倍数となる自然数$n$が存在する」

（中略）$x+1$個の自然数$a^0,a^1,\cdots,a^x$の中に$x$で割ったときの余りが等しいものが必ず1組は存在します。それを$a^i,a^j$($0\leq i<j\leq x$)とすると$a^j-a^i=a^i(a^{j-i}-1)$は$x$の倍数となり、$a$と$x$の倍数であることがわかります。
　実は補題の$n$の具体的な数値を定めた定理が存在し、「オイラーの定理」と呼ばれています。

「$a$と$x$が互いに素であるとき$a^{\phi(x)}-1$が$x$の倍数となる。ただし$\phi(x)$は$x$未満の自然数のうち$x$と互いに素なものの個数とする」

　この$\phi(x)$はオイラー数と呼ばれています。数xとが素数であるときには$a^{x-1}-1$が$x$の倍数であることになり、これは特に「フェルマーの小定理」と呼ばれています(「大定理」の方はあまりにも有名なあの定理です)。次の会報は「オイラーの定理」を用いたものです。

解法2
$9m$と$10$は互いに素な自然数になるので、「オイラーの定理」から
$$
10^{\phi(9m)}-1=\overbrace{99\cdots9}^{\phi(9m)個}
$$
は$9m$で割り切れます。つまり$9m\times n=99\cdots9$なる自然数$n$が存在し、
$$
m\times n=\overbrace{11\cdots1}^{\phi(9m)個}
$$
となり代位が示されます。もちろん、「オイラーの定理」の代わりに先程の「補題」を用いても同じです。

　また、割り切れない有理数は循環小数になることが知られていますが、その証明に使われるのも「鳩の巣原理」です。この循環小数を用いたのが次の解法です。

解法3
$9m$と$10$は互いに素なので、$\displaystyle\frac{1}{9m}$は純循環小数、すなわち小数点第1位から循環が始まる循環小数となります(証明は簡単なのでここでは省略します)。したがって、ある適当な自然数$n$があって
$$
\frac{1}{9m}=\frac{n}{99\cdots9}
$$
と書ける(つまり$n$は循環節)ので、
$$
m\times n=11\cdots1
$$
となり代位が示されます。
　解法2と解法3において$m$ではなく$9m$を用いてときました。$m$を用いて解く場合には、$m$が$3$の倍数であるかどうかで場合分けをする必要があります。たとえば解法2において$m=3$とすれば$10^{3-1}-1=99$は$3$の倍数ですがそれを$9$で割った$11$は$3$の倍数ではありません。

　さて、$m$は$10$と互いに素なので、一の位は$1,3,7,9$のいずれかになります。これらの数の特徴として、任意の$b\in\left\{0,1,\cdots,9\right\}$について$m\times x\equiv b\ ({\rm mod}\ 10)$なる$x\in\left\{0,1,\cdots,9\right\}$が存在する、というものがあります。つまりこれらの数の倍数を並べると、一の位には$0$から$9$まですべての数が現れるということです。最後の解法はこの声質と筆算による掛け算のプロセスから証明するものです。

解法4
まず$m\times x_1\equiv1\ ({\rm mod}\ 10)$なる(つまり$m$との積の一の位が$1$であるような)$x_1\in\left\{0,1,\cdots,9\right\}$をとり、$y_1=(mx_1-1)/10$とおきます。以下順番に$y_i+m\times x_{i+1}\equiv1\ ({\rm mod}\ 10)$なる$x_{i+1}\in\left\{0,1,\cdots,9\right\}$をとり、$y_{i+1}=\left( y_i+mx_{i+1}-1\right)/10$とおきます。すなわち、
$$
m\times\sum_{k=1}^ix_k10^{k-1}=y_i\times10^i+\overbrace{1\cdots1}^{i個}
$$
となります。ここで$0\leq x_i\leq 9$より$0\leq y_i<m$となりますから、$\left\{y_1,\cdots,y_{m+1}\right\}$において$y_i=y_j$($1\leq i>j\leq m+1$)なる$i,j$が少なくとも1組は存在します。その$i,j$について
\begin{eqnarray}
&m&\left( \sum_{k=1}^jx_k10^{k-1}-10^{j-i}\times\sum_{k=1}^ix_k10^{k-1}\right)\\
&\quad&=y_j\times10^j+\overbrace{11\cdots1}^{j個}-10^{j-i}( y_i\times 10^i+\overbrace{11\cdots1}^{i個})\\
&\quad&=\overbrace{11\cdots1}^{i個}
\end{eqnarray}
となり題意が示されます。

　意見すると何をしているのかわかりにくいかもしれません。$m$との積に$1$が並ぶように、定数の桁を1つずつ増やしていきます。$\left\{x_1,x_2,\cdots,x_i,\cdots\right\}$はその定数の各桁の数字を意味します。$\left\{y_1,y_2,\cdots,y_i,\cdots\right\}$は積の数字から$11\cdots1$を取り除いて残った数を意味します。筆算の要領で計算をするとわかりやくすなると思います。

（後略）
数学セミナー編集部編（2001）『エレガントな解答をもとむ selections』日本評論社 p178-p182.

読者の皆様への挑戦状！ぜひ解いてみて下さい！

以下の問題は次回挑戦します！

次の
$$
\sum_{k=1}^n\left( k^5+k^7\right)
$$
を$n$で表して下さい。

（ヒント）$\sum k^5$と$\sum k^7$を別々に求めては損です。もとのまま、電卓やパソコンで少し実験してみると、答が予想できます。正しく予想できれば証明は容易です。
数学セミナー編集部編（2001）『エレガントな解答をもとむ selections』日本評論社 p21

前回の問題は【１時間チャレンジシリーズ】挑戦㉔を御覧ください。

皆様の挑戦の結果を是非コメントで教えて下さい！

結

いかがでしたか？
今回は数セミの「エレガントな解答をもとむ」に挑戦してみる、という記事でした。

読者の皆様も是非一度挑戦してみて下さい！
そして、「読者の皆様への挑戦状」にも是非挑戦していただき、解答をコメントで教えて下さい！

質問、コメントなどお待ちしております！
どんな些細なことでも構いませんし、この記事に限らず、「定理〇〇の△△が分からない！」などいただければ全てお答えします！
お問い合わせの内容にもよりますが、ご質問はおおよそ３日以内にお答えします。
もし直ちに回答が欲しければその旨もコメントでお知らせください。直ちに対応いたします。

Twitterでもリプ、DM問わず質問、コメントを大募集しております！

他の「エレガントな解答をもとむ」の問題に挑戦してみたい方はぜひ以下の書籍をお買い求め下さい！