奇数の平方は8で割ると1余ることを示せ.
(2)\ \ 11,\ 111,\ 1111,\ $･･･$\ のように数字1のみが並ぶ2桁以上の整数は平方数ではない
\ \ ことを示せ. [\,津田塾大\,] レピュニット数の性質
すべての桁の数字が1である自然数を,\ repeated unit\ に由来し,\ レピュニット数という.
本項では,\ レピュニット数の性質に関する問題を取り上げる.
(1)\ \ 奇数を$2n+1\ (n:整数)$とおく.
$(2n+1)^2=4n^2+4n+1=4n(n+1)+1}$
連続2整数の積$n(n+1)$は偶数}なので,\ $4n(n+1)$は8の倍数である.
∴$ 奇数の平方は8で割ると1余る.
(2)\ \ [1]\ \ 11は8で割ると3余るので平方数ではない.
[2]\ \ 1が3桁以上並ぶとき,\ $1000m+111\ (m:0以上の整数)}$とおける.
\ \ $1000m+111=8(125m+13)+7$より,\ 8で割ると7余る}から平方数ではない.
∴$ 数字1のみが並ぶ2桁以上の整数は平方数ではない.
(1)より,\ 8で割ったときの余りが1ではないことを示せば,\ 平方数である可能性が消滅する.
ただし,\ レピュニット数は無限に多く存在するので,\ 1つずつ調べるわけにはいかない.
3桁以上のすべてのレピュニット数が1000m+111と統一的に表せる}ことがポイントになる.
これは,\ 8の倍数条件「下3桁が8で割り切れる」を導く場合と同様の考え方である.
千の位以上は1000=8･125より必ず8で割り切れるから,\ 8で割った余りは下3桁のみで決まる.}
本問から,\ 平方数のレピュニット数は1^2=1のみであることがわかる.
$p$を2,\ 5以外の素数とする.
(1)\ \ 異なる$p+1$個の自然数1,\ 11,\ 111,\ $･･･$,\ $111…1\ (1がp+1個並ぶ)$があるとき,\
\ \ その中に差が$p$の倍数となるような2個の自然数が存在することを示せ.
(2)\ \ $p$の倍数の中に$111…1$の形をしたものが存在することを示せ. \\
$p$で割ったときの余りは$0,\ 1,\ 2,\ ･･･,\ p-1$の$p$種類}である.
異なる$p+1$個の整数があるとき,\ 少なくとも2個は$p$で割ったときの余りが等しい.}
つまり,\ $p+1}$個の自然数の中に差が$p}$の倍数となるような2個の自然数が存在する.}
(2)\ \ 差が$p$の倍数となる2個の自然数を\ $\underbrace{111…1}_{a個}$,\ \ $\underbrace{111…1}_{b個}\ \ (a>b≧1)$\ とする.
この2数の差は,\ $\underbrace{111…1}_{a-b個}\underbrace{000…0}_{b個}=\underbrace{111…1}_{a-b個}×10^b\ (b:自然数)}$の形で表される.
ここで,\ $p$は2,\ 5以外の素数であるから,\ $p$と$10^b$は互いに素}である.
よって,\ $\underbrace{111…1}_{a-b個}\,はpの倍数}$である. \\
フェルマーの小定理を利用}\,]
\,$1がn個並ぶ自然数は,\ 10^n-1}{9}\ (n:自然数)と表せる.$
\,$n=p-1\ (p:2,\ 5以外の素数)}$のときを考える.
\,10と$p$は互いに素}であるから,\ フェルマーの小定理より $10^{p-1}-1≡0±od p}$
また $10^{p-1}-1}≡1^{p-1}-1≡0±od9}$
よって,\ $p$と9が互いに素}のとき,\ $10^{p-1}-1$は$9p$の倍数}である.
ゆえに,\ $p≠3}$のとき,\ $10^{p-1}-1}{9}\,はpの倍数}$である.
また,\ $p=3}$のとき,\ $111}=3･37$が条件を満たす.
レピュニット数の最も代表的な次の性質の証明で,\ 部屋割り論法を利用するのが標準解法である.
2,\ 5以外のすべての素数は,\ レピュニット数の素因数に現れる.}
言い換えると,\ 2,\ 5以外のすべての素数は,\ 何倍かするとレピュニット数になる.}
(1)\ \ 部屋割り論法}の項目で本質的に同じ問題を取り上げた.
(2)\ \ 具体例(p=7)を示しておく.
\ \ 異なる8個の整数1,\ 11,\ 111,\ 1111,\ 11111,\ 111111,\ 1111111,\ 11111111があるとする.
\ \ (1)より,\ この中に差が7の倍数となる2数が必ず存在する.
\ \ 実際,\ 11111111-11=11111100=7×1587300である.
\ \ 11111100=111111×10^2\,において10^2\,は7の倍数ではないから,\ 111111が7の倍数}である.
\ \ 本問には,\ フェルマーの小定理を利用するより本質的な別解が存在する.
\ \ フェルマーの小定理 a^{p-1}≡1±od p (p:素数,\ aとpは互いに素)}
\ \ また,\ レピュニット数が\,10^n-1}{9}\,の形で表せることを利用する.
\ \ レピュニット数は,\ 1111=1000+100+10+1のようにして和に分割できる.
\ \ n桁のレピュニット数は初項1,\ 公比10,\ 項数nの等比数列の和(数 B:数列)である.
\ \ よって,\ 等比数列の和の公式を用いて\ 1(10^n-1)}{10-1}=10^n-1}{9}\ が導かれる.
\ \ 数列を未学習でも,\ 具体的に\,10^4-1}{9}=9999}{9}=1111と考えると直感的に理解できる.
\ \ 定理より10^{p-1}≡1,\ よって10^{p-1}-1≡0±od pなので,\ 10^{p-1}-1はpの倍数}である.
\ \ 10^{p-1}-1は9の倍数}である.\mod9で確認したが,\ 10^{p-1}-1=99…9よりほぼ自明である.
\ \ pの倍数かつ9の倍数でpと9が互いに素ならば,\ 9pの倍数である.
\ \ 素数pの中で3のみが9と互いに素ではないから,\ 3の場合のみ分けて考えることになる.
\ \ 別解から,\ pの倍数となるレピュニット数は\ 10^{p-1}-1}{9}=\underbrace{111…1}_{p-1個}\ }であることがわかる.
\ \ 例えば,\ \underbrace{111…1}_{12個}\,は13の倍数である.
自然数$n$に対し,\ $R_n=\underbrace{111…1}_{n個}=10^n-1}{9}$\ と定める. [-.5zh]
\ \ (1)\ \ $R_{n+1}$と$R_n$が互いに素であることを示せ.
\ \ (2)\ \ $m$を自然数とする.\ \ $n$が$m$の倍数のとき,\ $R_n$が$R_m$の倍数となることを示せ.
\ \ (3)\ \ $m$を0以上の整数とする.
(3)}\ \ \ \ $R_{3^m}$は$3^m$の倍数だが,\ $3^{m+1}$の倍数ではないことを数学的帰納法を用いて示せ. \\
(1)\ \ $R_{n+1},\ R_n$は2,\ 5の倍数ではない.
$R_{n+1},\ R_n$が2,\ 5以外の素数の公約数$p$をもつと仮定}する.
このとき,\ $R_{n+1}=pk,\ R_n=pl\ (p:2,\ 5以外の素数\,;\ k,\ l:自然数)$とおける.
差をとると $R_{n+1}-R_n=10^n=p(k-l)}$
これは,\ $pが2,\ 5以外の素数であることと矛盾}する.$
∴ R_{n+1}\,とR_n\,は互いに素}である.$}
互いに素の証明では,\ 素数の公約数をもつと仮定して矛盾を示す}とよいのであった.
ただし,\ 本問の場合,\ 2,\ 5以外の素数}とすることが重要になる.
レピュニット数に関する証明では,\ 111…1の形で考えるか,\ 10^n-1}{9}\,の形で考えるかの2択がある.
本問の場合は111…1の形で考えた方が手っ取り早い.
R_{n+1}-R_n=\underbrace{111…1}_{n+1個}-\underbrace{111…1}_{n個}=1\underbrace{000…0}_{n個}=10^n
(2)\ \ $n=km\ (k:自然数)}$とおける.
∴$ $(10^m)^{k-1}+(10^m)^{k-2}+･･･+1は整数なので,\ R_n\,はR_m\,の倍数である.}$} \\
本問は\,10^n-1}{9}\,の形で考えるほうが楽である.
何とかしてR_m\,の形を作り出すことを考え,\ 10^m=xとして次の公式を適用する.
x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+･･････+xy^{n-2}+y^{n-1})}
特に,\ y=1のとき x^n-1=(x-1)(x^{n-1}+x^{n-2}+･･････+x+1)}
整数分野では,\ この公式を用いてx^n-y^n\,がx-yの倍数であることを示す問題が少なくない.
具体例(k=3,\ m=5)を111…1の形で示しておく.
R_{15}=R_{3･5}=\underbrace{11111}_{5個}\underbrace{11111}_{5個}\underbrace{11111}_{5個}=\underbrace{11111}_{5個}×10^{5･2}+\underbrace{11111}_{5個}×10^5+\underbrace{11111}_{5個} [-.7zh]
R_{15}=R_{3･5=\underbrace{11111}_{5個}\ \{(10^{5})^2+10^5+1\}=R_5\{(10^{5})^2+10^5+1\}
レピュニット数が素数となるとき,\ これをレピュニット素数}という.
本問から,\ nが合成数のときR_n\,も合成数となる}ことがわかる.
よって,\ R_n\,がレピュニット素数であるためには,\ nが素数であることが必要条件である.
十分条件ではない.\ つまり,\ nが素数だからといって,\ R_n\,も素数になるとは限らない.
2021年現在,\ レピュニット素数はn=2,\ 19,\ 23,\ 317,\ 1031の場合しか知られていない.
レピュニット素数が無限に多く存在するかは未解決である.
m=0}$のとき $R_{3^0}=R_1=1$は$3^0=1$の倍数だが,\ $3^{0+1}=3$の倍数ではない. m=k}$のとき $R_{3^k}$は$3^k$の倍数だが,\ $3^{k+1}$の倍数ではないと仮定}する.
よって,\ $R_{3^{k+1$は$3^{k+1}$の倍数だが,\ $3^{k+2}$の倍数ではない. [1],\ [2]\,より,\ すべての0以上の整数$m}$に対して,\ 題意の性質が成り立つ. \\
m=0}$のとき $R_{3^0}=R_1=1$は$3^0=1$の倍数だが,\ $3^{0+1}=3$の倍数ではない.
{10^{3^k}-1}{9}$は$3^k$の倍数だが,\ $3^{k+1}$の倍数ではないと仮定}する.
\ \ このとき,\ $R_{3^k}=10^{3^k}-1}{9}=3^kq\ \ (q:3の倍数でない自然数)$とおける.
$R_{3^{k+1$は$3^{k+1}$の倍数だが,\ $3^{k+2}$の倍数ではない.
∴$ [1],\ [2]\,より,\ すべての0以上の整数$m}$に対して,\ 題意の性質が成り立つ.
3^m\,桁のレピュニット数R_{3^m}\,は3^m\,の倍数}であることの証明である.
例えば,\ 3桁のとき111=3･37,\ \ 3^2=9桁のとき111111111=9･37･333667である.
レピュニット数R_n\,には,\ R_9\,はR_3\,で,\ R_{27}\,はR_9\,で構成されるという逐次的構造}がある.
これを考慮すると,\ 数学的帰納法(数 B)による証明が有効である.\ 数 B学習済みを前提とする.
基本的な流れは(2)と同様である.\ ただし,\ 111…1の形で考えるほうを本解とした.
m=k+1のとき,\ (2)と同様にして,\ まずR_{3^k}\,の倍数,\ つまり3^k\,の倍数であることが示される.
後は,\ R_{3^k}\,以外の部分が3の倍数であり,\ かつ3^2=9の倍数でない}ことを示せばよい.
10^n-1}{9}\,の形で考えるとき,\ 倍数条件を文字で設定して数式に反映させる}ことになる.
ただし,\ 10^{3^k}-1}{9}=3^kq\,をこのままの形でR_{3^{k+1\,の式に適用させようとしても難しい.
この場合,\ 仮定のほうの式をあらかじめ変形してから適用する}とよいのであった.
後はa^m× a^n=a^{m+n},\ \ (a^m)^n=a^{mn}\ に注意してひたすら計算し,\ 3^{k+1}\,をくくり出せばよい.
