当ＨＰがいつもお世話になっているＨＮ「ぽっぽ」さんからの出題です。
（平成２３年３月１２日付け）
９より大きく、３の倍数でない自然数 ｎ について、ｍ 桁の全ての位が 0 と 1 で構成
される数（たとえば、１０００１１・・・のような形で、ｍ＜ｎ/２ とする。）が、ｎ で割り切れ
るような ｍ 桁の数が存在することを示せ。
問題の趣旨を理解するために、いくつか実験してみた。
例 ｎ＝１０ のとき、２桁の数 １０ は、１０で割り切れる。
ｎ＝１１ のとき、４桁の数 １１１１ は、１１で割り切れる。
ｎ＝１３ のとき、４桁の数 １００１ や５桁の数 １１０１１ は、１３で割り切れる。
（答え） 当ＨＰがいつもお世話になっているＨＮ「DD++」さんが考察されました。５年以上放置
されていた問題で、DD++さんに感謝します。（平成２８年９月１９日付け）
先に補題を1つ。
ｋを5以上の自然数とする。1、2、3、……、k というｋ個の絶対値それぞれに「+」また
は「-」の符号をつけるとき、どのように符号をつけても、ｋ個の数のうちいくつかの和で
2k+1 の倍数であるものが存在する
例 ＋１、＋２、＋３、−４、＋５ に対して、＋１＋２＋３＋５＝＋１１は１１の倍数
−１、＋２、＋３、−４、＋５ に対して、−１＋２＋３−４＝０ は１１の倍数
（証明） 1は、「+」として一般性は失わない。
(1) 2が、「+」の場合
3以上の中に「-」があるならば、初めて「-」がついた絶対値を j として、+1,+(j-1),-j の和が
条件を満たす。実際に、+1+(j-1)-j=0 は、2k+1 の倍数。
3以上が全て「+」であれば、+2,+(k-1),+k の和が条件を満たす。実際に、+2+(k-1)+k=2k+1
は、2k+1 の倍数。
(2) 2が、「-」、3が、「+」の場合
4以上の中に「-」があるならば、初めて「-」がついた絶対値を j として、+1,+(j-1),-j の和が
条件を満たす。実際に、+1+(j-1)-j=0 は、2k+1 の倍数。
4以上が全て「+」であれば、+1,-2,+3,+(k-1),+k の和が条件を満たす。
実際に、+1-2+3+(k-1)+k=2k+1 は、2k+1 の倍数。
(3) 2が、「-」、3が、「-」の場合
4以上の中に「+」があるならば、初めて「+」がついた絶対値を j として、+1,-2,-(j-1),+j の和
が条件を満たす。実際に、+1-2-(j-1)+j =0 は、2k+1 の倍数。
4以上が全て「-」であれば、-2,-(k-1),-k の和が条件を満たす。
実際に、-2-(k-1)-k=−(2k+1) は、2k+1 の倍数。
以上により示された。 （証終）
これを用いて証明します。
（証明） nが、9より大きく3で割り切れない奇数の場合。
1,10,100,1000,……,10^{(n-3)/2} という(n-1)/2 個の数をそれぞれnで割り、余りを求めます。
ただし、最小非負剰余ではなく絶対値最小剰余で計算します。
（例えば8÷3は商が3で余り-1、のように余りは正でなくてもよいのでその絶対値が最も小さ
くなるようにする）
(1) その中で余りが0になったものがあれば、その数が条件を満たします。
例 n=25 のとき、100÷25=4あまり0なので、100が条件を満たす。
(2) その中で同じ剰余になった2つがあれば、その差を9で割った数が条件を満たします。
（nが9と互いに素であるのがポイント）
例 n=37のとき、1÷37=0 あまり 1、1000÷37=27 あまり 1 なので、(1000-1)/9=111が条件
を満たす。
(3) その中で符号は逆で絶対値が等しい剰余になった2つがあれば、その和が条件を満た
します。
例 n=13のとき、1÷13=0 あまり 1、1000÷13=77 あまり -1 なので、1000+1=1001が条件を
満たす。
(4) 上記3つのいずれにも当てはまらない場合、剰余の絶対値は、1から(n-1)/2まで全て1
つずつ存在するので、補題よりいくつかの数の剰余の和でnの倍数になるものが存在し
ます。その和をもとの10の累乗で表現した数が条件を満たします。
例 n=17のとき、1÷17=0 あまり 1、10÷17=1 あまり -7、100÷17=6 あまり -2、
1000÷17=59 あまり -3、10000÷17=588 あまり 4、100000÷17=5882 あまり 6、
1000000÷17=58824 あまり -8、10000000÷17=588235 あまり 5
なので、補題より、あまりが +1,-2,-3,+4 になるものを選んで、1+100+1000+10000=11101が
条件を満たす。
以上4つのいずれかの方法で、nが9より大きく3で割り切れない奇数の場合については条
件を満たす数を作れることが示されました。
次に、n=10,14,16の場合。
10は10の約数、14は10010の約数、16は10000の約数で、いずれも桁数はn/2より小さく、
条件を満たします。
最後に、nが18より大きく3の倍数でない偶数の場合。
n=2^p×a（aは9より大きい3の倍数でない奇数もしくは10,14,16）と書ける。
n=aのとき条件を満たす数をAとすると、10^p×Aは明らかに桁数が2^(p-1)×aより小さい
0と1で構成された2^p×aの倍数なので、条件を満たします。
以上により、全ての9より大きく3の倍数でない自然数について命題は示されました。 （証終）
#証明はできた（たぶん）ものの、あまりに美しくない。もっと綺麗な方法がありそうですが……。
以下、工事中