整数問題は好きです、なぜなら、解きながら勝手に数の本質に迫っているような錯覚に陥るからです。

私にとって、「数の本質」は「自然の本質」や「自然の真理」そのもので、なにか神秘的なものを感じるのですよ。

ガウスの言葉にある「数学は科学の女王であり、整数論は数学の女王である」というのを感じざる得ないのです。


今回も難問でした。


難問中難易度☆☆☆☆

【問題】
正の整数$ a,b $は10進法で表すといずれも$ 2n $桁となり、最上位の数字は0ではない。さらに、次の3つの条件が成り立つ。

　(1)$ a $の上$ n $桁と$ b $の下$ n $桁とは等しく、$ a $の下$ n $桁と
　　　$ b $の上$ n $桁とは等しい。
　(2)$ a < b $である。
　(3)$ b $は$ a $の倍数である。

このような$ a,b $をすべて求めよ。

例えば、$ a=1234,b=3412 $のとき、(1)、(2)は成り立つが、(3)は成り立たない。

【証明】
条件(1)より、$ n $桁の数$ x,y $を用いて
\begin{eqnarray}
\left\{ \begin{array}{l}
a = 10^{ n } x + y \\
b = 10^{ n } y + x \\
\end{array} \right.
\end{eqnarray}
条件(2)より$ x < y $

条件(3)より、ある2以上9以下の整数$ m $が存在して
$$ 10^{ n } y + x = m ( 10^{ n } x + y ) \ \ \cdots (A) $$
の、3つが成り立つ。

$ (A) $の両辺に$ 10^{ n } x + y $を足すと
$$ ( x+y )( 10^{ n }+1 ) = ( m+1 )( 10^{ n } x + y ) \ \ \cdots (B) $$


ここで、$ m+1 , 10^{ n } + 1 $が互いに素であると仮定すると、
$$ 10^{ n }x + y \equiv 0 \ \ \pmod{ 10^{ n } + 1 } $$
なので、
$$ x( 10^{ n } + 1) \equiv x - y \ \ \pmod{ 10^{ n } + 1 } $$
よって
$$ x \equiv y \ \ \pmod{ 10^{ n } + 1 } $$
これは、$ x,y $はどちらも$ n $桁なので$ x,y < 10^{ n } $で、$ x < y $であることに矛盾する。

よって、$ m+1 , 10^{ n } + 1 $は共通の素因数をもち、その素因数としてありうるのは2,3,5,7のいずれかである。

しかし、$ 10^{ n } + 1 $は2,3,5の倍数になりえないので、$ m+1 , 10^{ n } + 1 $の共通の素因数は7である。

これより、$ 2 < m < 9 $なので、$ m =6 $である。


ここで、$ \displaystyle k = \frac{ 10^{ n } + 1 }{ 7 } $とおくと$ (B) $より
$$ ( x + y ) \cdot 7k = 7 \cdot \{ ( 7k - 1 )x + y \} $$
より
$$ 5kx = ( k-1 )( y-x ) \ \ \cdots (C) $$
となる。

$ 7k = 10^{ n } + 1 \equiv 1 \pmod{ 5 }\ $より$\ k \equiv 3 \pmod{ 5 } \ $なので、5と$ k-1 $は互いに素である。

また、$ k $と$ k-1 $は互いに素なので、$ 5k $と$ k-1 $も互いに素であり、$ (C) $より$ y-x $は$ 5k $の倍数であることがわかる。

これと、$ 0 < y-x < 10^{ n } + 1 = 7k $より、$ y - x = 5k $となり、このとき$ (C) $より$ x = k-1 $、よって$ y = 6k-1 $となる。


これより
\begin{eqnarray*}
a &=& 10^{ n } x + y \\
&=& 10^{ n }( k-1 ) + ( 6k-1 ) \\
&=& 10^{ n } ( \frac{ 10^{ n } + 1 }{ 7 } - 1 ) + ( 6 \cdot \frac{ 10^{ n } + 1 }{ 7 } - 1 ) \\
&=& \frac{ 1 }{ 7 } ( 10^{ 2n } - 1 ) \\
b &=& ma = \frac{ 6 }{ 7 } ( 10^{ 2n } - 1 )
\end{eqnarray*}
ここで、$ 10^{ n } + 1 $が7の倍数であることより、7の倍数判定から
$$ n \equiv 3 \pmod{ 6 } $$

【7の倍数判定】
ある数を$ abcdefghijkl $として、一の位から3桁ずつ区切り$ abc,def,ghi,jkl $とする。
区切られたそれぞれの3桁の数を独立した数と考え、左から奇数番目にある数の和と偶数番目にある数の和の差、すなわち
$$ S = (abc + ghi ) - ( def + jkl ) $$
が7で割り切れれば、その数は7で割り切れる。

今回の場合、$ 100 \cdots 001 $において、$ S = 0,9,99,-2,-11,-101 $のいずれかであるが、このうち7で割り切れるのは$ S = (abc + ghi ) - ( def + jkl ) = 0 $。

これより、$ 10^{ n } + 1 $が1,001、1,000,000,001、1,000,000,000,000,000,001、すなわち$ n $が6で割って3余る数のときとなる。

逆に、$ n \equiv 3 \pmod{ 6 } $のとき、$ a = \frac{ 1 }{ 7 } ( 10^{ 2n } - 1 ) $と$ b = \frac{ 6 }{ 7 } ( 10^{ 2n } - 1 ) $は条件をみたす。

これより、求める解は
$$ ( a,b ) = ( \frac{ 1 }{ 7 } ( 10^{ 2n } - 1 ) , \frac{ 6 }{ 7 } ( 10^{ 2n } - 1 ) ) $$
かつ、$ n $は$ n \equiv 3 \pmod{ 6 } $を満たす正の整数である。