インテジャーズ

インテジャーズ

数、特に整数に関する記事。

20:交代的数

20という数の面白い性質を私はあまり知りません(自称『数のエンターテイナー』として実に恥ずかしい)。

調べてみると次のような20の性質が見つかりました:

合成数mに対して、\displaystyle f(m) := m+\sum_{p < m}p を考える(pは素数)。このとき、f(m)が素数になるような最小のm20である。

実際、

\displaystyle f(4)=9

\displaystyle f(6)=16

\displaystyle f(8)=25

\displaystyle f(9)=26

\displaystyle f(10)=27

\displaystyle f(12)=40

\displaystyle f(14)=55

\displaystyle f(15)=56

\displaystyle f(16)=57

\displaystyle f(18)=76

\displaystyle f(20)=97

となっています。


私がもともと知っていた知識の中で20についてピンとくるのは次の性質です:

定義 自然数が交代的数であるとは、その10進法表記において、各隣合う桁の偶奇が異なるときにいう。

定理 n20の倍数ではないような自然数とする。このとき、ある自然数mをとってnmを交代的数にすることができる。

例えば、4620の倍数でも交代的数でもないですが、46\times 5=230は交代的数です。
また、20の倍数については何倍しても下二桁がともに偶数になります。

なお、この定理を証明させるのが2004年の国際数学オリンピック第6問です。

定理の証明

補題1 任意の自然数kに対して、2^{k+1}で割り切れるような2k桁の交代的数が存在する。

証明. 実際には最高位の桁は常に1であるようにできる。これをkに関する数学的帰納法で証明する。k=1のときは16が題意を満たす。
k-1のときに題意が成り立つと仮定する。すなわち、2k-2桁の整数\displaystyle N=\sum_{i=0}^{2k-3}a_i10^i \ (0 \leq a_i \leq 9)が交代的数であって、N2^{2k-1}で割り切れると仮定する。このとき、N/2^{2k+1}\bmod{4}で分類して2k桁の数N'を構成する。

\displaystyle N/2^{2k-1} \equiv 0 \pmod{4}のとき N' := 16\cdot 10^{2k-2}+Nとすると、

\displaystyle \frac{N'}{2^{2k-1}} =8\cdot 5^{2k-1} + \frac{N}{2^{2k-1}} \equiv 0 \pmod{4}

なので、帰納法の仮定と合わせてN'2^{2k+1}で割り切れるような2k桁の交代数である。以下、同様に合同関係を示していく。

\displaystyle N/2^{2k-1} \equiv 1 \pmod{4}のとき N' := 14\cdot 10^{2k-2}+Nとすると、

\displaystyle \frac{N'}{2^{2k-1}} =7\cdot 5^{2k-1} + \frac{N}{2^{2k-1}} \equiv 3+1 \equiv 0 \pmod{4}.

\displaystyle N/2^{2k-1} \equiv 2 \pmod{4}のとき N' := 12\cdot 10^{2k-2}+Nとすると、

\displaystyle \frac{N'}{2^{2k-1}} =6\cdot 5^{2k-1} + \frac{N}{2^{2k-1}} \equiv 2+2 \equiv 0 \pmod{4}.

\displaystyle N/2^{2k-1} \equiv 3 \pmod{4}のとき N' := 18\cdot 10^{2k-2}+Nとすると、

\displaystyle \frac{N'}{2^{2k-1}} =9\cdot 5^{2k-1} + \frac{N}{2^{2k-1}} \equiv 1+3 \equiv 0 \pmod{4}.

Q.E.D.

補題2 kを任意の自然数とする。このとき、kが奇数ならばk桁の、kが偶数ならばkまたはk-1桁の交代的数であって、5^kで割れるような奇数が存在する。

証明. kに関する帰納法で証明する。k=1のときは5が題意を満たす。k-1のときに題意が成り立つと仮定して、k\geq 2の場合にも成立することを証明する。
kが偶数のとき
帰納法の仮定によって、5^{k-1}で割れるようなk-1桁の交代的奇数Nが存在する(最高位の数は奇数)。N/{5^{k-1}}\equiv r \pmod{5}r \in [0, 4] とする。r=0のときはN':=Nとするとこれはk-1桁の交代的奇数であり、5^{k}で割り切れる。r\neq 0のときは更に場合分けをする:

k \equiv 0 \pmod{4}のとき
N':=(10-2r)10^{k-1}+Nとするとこれはk桁の交代的奇数であり、

\displaystyle \frac{N'}{5^{k-1}} = (10-2r)2^{k-1}+\frac{N}{5^{k-1}} \equiv -2r\cdot 3+r \equiv 0 \pmod{5}

なので5^kで割り切れる。

k \equiv 2 \pmod{4}のとき
N':=2r\cdot 10^{k-1}+Nとするとこれはk-1桁の交代的奇数であり、

\displaystyle \frac{N'}{5^{k-1}}=2r\cdot 2^{k-1}+\frac{N}{5^{k-1}} \equiv 4r+r \equiv 0 \pmod{5}

なので5^kで割り切れる。

kが奇数のとき
帰納法の仮定によって、5^{k-1}で割れるようなk-1桁またはk-2桁の交代的奇数Nが存在する。Nk-2桁の数の場合は最高位の数が0k-1桁の数であるとみなすことによって、Nの最高位の数は偶数である。N/5^{k-1}\equiv r \pmod{5}r \in [0, 4] とする。

k \equiv 1 \pmod{4}かつrが偶数のとき
N':=(5-r)10^{k-1}+Nとするとこれはk桁の交代的奇数であり、

\displaystyle \frac{N'}{5^{k-1}} = (5-r)2^{k-1}+\frac{N}{5^{k-1}} \equiv -r + r \equiv 0 \pmod{5}

なので5^kで割り切れる。

k \equiv 1 \pmod{4}かつrが奇数のとき
N':=(10-r)10^{k-1}+Nとするとこれはk桁の交代的奇数であり、

\displaystyle \frac{N'}{5^{k-1}} = (10-r)2^{k-1}+\frac{N}{5^{k-1}} \equiv -r + r \equiv 0 \pmod{5}

なので5^kで割り切れる。

k \equiv 3 \pmod{4}かつrが偶数のとき
N':=(5+r)10^{k-1}+Nとするとこれはk桁の交代的奇数であり、

\displaystyle \frac{N'}{5^{k-1}} = (5+r)2^{k-1}+\frac{N}{5^{k-1}} \equiv 4r + r \equiv 0 \pmod{5}

なので5^kで割り切れる。

k \equiv 3 \pmod{4}かつrが奇数のとき
N':=r\cdot 10^{k-1}+Nとするとこれはk桁の交代的奇数であり、

\displaystyle \frac{N'}{5^{k-1}} = r\cdot 2^{k-1}+\frac{N}{5^{k-1}} \equiv 4r + r \equiv 0 \pmod{5}

なので5^kで割り切れる。

以上で全てのケースにおいて帰納法が機能している。 Q.E.D.

問題 n, mを自然数とする。このとき、
\displaystyle 10^n-1 \mid 10^m-1 \Longrightarrow n \mid m
を示せ。

ヒント. mnで割った余りをrとして、r=0を示せばよい。

この問題より、10^n-1 \mid 10^m-1ならば、10進法表記で

\displaystyle \frac{10^m-1}{10^n-1} = 1\underbrace{0\cdots 01}_{n}\cdots \underbrace{0\cdots 01}_{n}

となることがわかる。

定理の証明. n20の倍数ではないような自然数とする。このとき、非負整数kおよび2, 5で割り切れない自然数mが存在してn=2^kmn=5^km、または10\cdot 5^kmのいずれかの形でnを表示することができる。交代的な倍数が存在することを示せばよいので、k \geq 1と仮定してn=2^kmおよび10\cdot 5^kmの場合に示せば十分である。
n=2^kmの場合
補題1より2k-2桁の交代的数Nであって2^kで割り切れるような自然数が存在する(最高位の数は1)。Eulerの定理より

10^{\varphi (m(10^{2k-2}-1))} \equiv 1 \pmod{m(10^{2k-2}-1)}

であるから(\varphiはEulerのトーシェント関数)、

\displaystyle \frac{10^{\varphi (m(10^{2k-2}-1))}-1}{10^{2k-2}-1} = 1\underbrace{0\cdots 01}_{2k-2}\cdots \underbrace{0\cdots 01}_{2k-2}

mの倍数である。従って、

\displaystyle \frac{10^{\varphi (m(10^{2k-2}-1))}-1}{10^{2k-2}-1}N = \fbox{N}\cdots \fbox{N}

は交代的なn=2^kmの倍数である(右辺は10進法表記でNが複数回並んだ数)。

n=10\cdot 5^kmの場合
最高位の数として0も認めることよって、補題1より偶数桁(2d桁としよう)の交代的奇数Nであって5^kで割り切れるような自然数が存在する(最高位の数は偶数)。Eulerの定理より

10^{\varphi (m(10^{2d}-1))} \equiv 1 \pmod{m(10^{2d}-1)}

であるから(\varphiはEulerのトーシェント関数)、

\displaystyle \frac{10^{\varphi (m(10^{2d}-1))}-1}{10^{2d}-1} = 1\underbrace{0\cdots 01}_{2d}\cdots \underbrace{0\cdots 01}_{2d}

mの倍数である。従って、

\displaystyle \frac{10^{\varphi (m(10^{2k-2}-1))}-1}{10^{2k-2}-1}\cdot 10N = \fbox{N}\cdots \fbox{N} \ 0

は交代的なn=10\cdot 5^kmの倍数である(右辺は10進法表記で一桁目が0で二桁目以降の部分にNが複数回並んだ数。最高位が0の可能性もあるが、上から二番目の桁は0でない)。 Q.E.D.