初等整数論の最も基礎的な基本定理

だいたいの「初等整数論」と呼ばれる本を開いてみると、次のような定理が紹介されているのを目にするだろう（混乱を防ぐため、以下では、自然数は「0を含まない正の整数」とする）。

負の整数以外の集まりから、二つの数（これらをそれぞれa, bと名付け、aは自然数)を取ってきて、下のような数式を作る。

b = qa + r , rは負の整数以外

上の式を満たすq, rがただ一組みだけ存在する。

一般的にこれを 「除法の可能性と一意性」 の定理としている。日本語に直せば、要するに「ある数は、与えられた数の倍数と、その余りで表現できる」ということだ。この証明はあまりにも基礎的なので省略するが、この定理が有理数から実数に変換する場合に使われている、とも捉えられる。

有理数を実数に変換するとき、私たちは「元の数を、与えられた数で割る。余りが0でなければ、その余りを十倍にして足す」という形で求める。上の式で言われているaを商と呼ぶ。例えば、31/7であるならば、「31を7で割れば、商は4、余りが3なので、それを十倍にして30。30の商は4であり、余りは2なので、それを10倍して20。すると商は2なので……」となり、31/7 は　4.42...。となる。

小数点を出すときの作業を考える

この操作を考えた場合、私たちは下のようなことをやっていると考えられる。元の数をr{n}とおき、rをr{n+1}といったような構造として捉えてみる。

 r{1} = q{1} * a + r{2}
 r{2} * 10 = q{2} * a + r{3}
 r{3} * 10 = q{3} * a + r{4}
 ...
 r{n} * 10 = q{n} * a + r{n+1}

このとき、r{j}とr{k}で表現できるような、ある区間j,k (j < k, どちらも自然数) を2つ取った場合(それぞれを、j{1}、j{2}、k{1}、k{2})、もしr{ j{i} } = r { j{2} } であるならば、r { k{1} } = r { k{2} } ということが出来る。

もし「r { j{1} }と r { j{2} }が一緒であるのに、r { k{1} } と r { k{2} }が異なる」と仮定してみよう。まずr { k{1} } と r {k {2} }が違うならば、この余りになった元の数も違う筈だ（一意性のため）。このようにr { i{1} }とr{ i{2} }まで遡っていった場合、結局r{ i{1} }もr{ i{2} }も違うことになるため、仮定と矛盾する。

これをもう少し一般的な法則にすると、「前に同じ余りが出てきた場合、次に出てくる余りも同じになる。それは次に同じ余りが出てくるまで変わらない」ということになる。直感的に言えば、さきほどの有理数から小数点の操作のときに出てくる余りそれぞれに t{1}, t{2}... t{n} と割り振った場合、次のようになる場合があるということだ:

t{1} -> t{2} -> t{3} -> t{1} -> t{2} -> t{3} ....

プログラムを組む方針を定める

ここまで考えてわかることは、「循環小数点の桁数」だけ考えるならば、この余りの数だけを記録していけばいいことになる。そして、同じ余りが出てきたときに、記録した余りにバツを付けていけばよく、そして再びバツをつけた余りが出てきたときに「その区間が循環小数点になっている」ということが出来る。

とはいえ、バツを付けている間は、同じ余りが出てくるまで「バツを付けておらず、記録もされていない余りが出てくる」ということはありえない（上の証明により）。従って「バツを付け始める」ということは、「消し始めたというフラグを立てて、記録から余りを消していき、再びその記録に無い余りが出てきたら、二度目の循環が始まった」ということが出来る。

プログラミングは省略するけれども、その方針で考えていったら、いわば1000以下で最も循環する数というのが出てきたので、無事解答ができたのであった。