循環小数と分数

方針：割り算の商と余りがただ 1 組に決まること（整数の割り算と互除法 の割り算の定理）を、$10^ka$ と $10^{k+1}a$ の割り算に使う。
段 1（1 の証明）。$10^ka$ を $n$ で割った商を $q_k$ とすると $10^ka=nq_k+r_k$、$0\le r_k< n$ である。両辺を $n$ で割ると
$$ 10^kx=q_k+\frac{r_k}n,\qquad 0\le\frac{r_k}n<1 $$
である。$q_k$ は整数で、$q_k\le10^kx< q_k+1$ なので、$q_k=\lfloor10^kx\rfloor$ である。
段 2（2 の証明）。$10r_k$ を $n$ で割った商を $e$、余りを $r'$ とすると $10r_k=ne+r'$、$0\le r'< n$ である。段 1 の式を $10$ 倍して代入すると
$$ 10^{k+1}a=10nq_k+10r_k=n(10q_k+e)+r' $$
である。$0\le r'< n$ なので、これは $10^{k+1}a$ を $n$ で割った式であり、商と余りの一意性により $q_{k+1}=10q_k+e$、$r_{k+1}=r'$ である。def-rdf-digit と段 1 により $d_{k+1}=q_{k+1}-10q_k=e$ である。$0\le10r_k<10n$ なので $0\le e\le9$ である。$r_{k+1}=r'=10r_k-ne$ である。
段 3（3 の証明）。$y=\dfrac{r_k}n$ とおく。段 1 により $y=10^kx-q_k$ である。$j\ge0$ について $10^jy=10^{k+j}x-10^jq_k$ で、$10^jq_k$ は整数なので
$$ \lfloor10^jy\rfloor=\lfloor10^{k+j}x\rfloor-10^jq_k $$
である（整数を引いても、床は同じ整数だけ減る）。これを def-rdf-digit に代入すると、$y$ の小数第 $j$ 位の数字は
$$ \lfloor10^jy\rfloor-10\lfloor10^{j-1}y\rfloor=\bigl(\lfloor10^{k+j}x\rfloor-10^jq_k\bigr)-10\bigl(\lfloor10^{k+j-1}x\rfloor-10^{j-1}q_k\bigr)=d_{k+j} $$
である。$10^jq_k$ の項が打ち消し合った。
段 4（4 の証明）。$y$ の数字を $e_1,e_2,\dots$ とする。def-rdf-digit の式 $\lfloor10^iy\rfloor=10\lfloor10^{i-1}y\rfloor+e_i$ を $i=1,2,\dots,j$ の順に使うと、$\lfloor y\rfloor=0$ から始めて
$$ \lfloor10^jy\rfloor=e_110^{j-1}+e_210^{j-2}+\cdots+e_j $$
である。$y'$ も数字が同じなので $\lfloor10^jy'\rfloor=\lfloor10^jy\rfloor$ である。$10^jy$ と $10^jy'$ はどちらも同じ整数 $N$ 以上 $N+1$ 未満にあるので、差は $1$ 未満である。つまり $|y-y'|<10^{-j}$ がすべての $j$ で成り立つ。$|y-y'|>0$ なら、$10^{-j}<|y-y'|$ となる $j$ があるので矛盾する。よって $y=y'$ である。$\square$

方針：2 から 1 は、lem-rdf-remainder の 2（次の数字と次の余りは今の余りだけで決まる）を使う。1 から 2 は、lem-rdf-remainder の 3 と 4（同じ数字の列をもつ 2 数は等しい）を使う。
段 1（2 ならば 1）。$r_{s+t}=r_s$ と仮定する。まず、$j\ge0$ のすべてについて $r_{s+t+j}=r_{s+j}$ であることを $j$ についての数学的帰納法で示す。$j=0$ のときは仮定そのものである。ある $j$ で $r_{s+t+j}=r_{s+j}$ とすると、lem-rdf-remainder の 2 により
$$ r_{s+t+j+1}=10r_{s+t+j}-n\left\lfloor\frac{10r_{s+t+j}}n\right\rfloor=10r_{s+j}-n\left\lfloor\frac{10r_{s+j}}n\right\rfloor=r_{s+j+1} $$
である。よって $j+1$ でも成り立つ。
次に数字を比べる。$j\ge0$ について、lem-rdf-remainder の 2 により
$$ d_{s+t+j+1}=\left\lfloor\frac{10r_{s+t+j}}n\right\rfloor=\left\lfloor\frac{10r_{s+j}}n\right\rfloor=d_{s+j+1} $$
である。$k=s+j+1$ とおくと、これは $k>s$ のすべての $k$ で $d_{k+t}=d_k$ ということである。よって $x$ は $(s,t)$ で循環する。
段 2（1 ならば 2）。$x$ が $(s,t)$ で循環すると仮定する。lem-rdf-remainder の 3 により、$\dfrac{r_s}n$ の小数第 $j$ 位の数字は $d_{s+j}$、$\dfrac{r_{s+t}}n$ の小数第 $j$ 位の数字は $d_{s+t+j}$ である（$j\ge1$）。$s+j>s$ なので、仮定から $d_{s+t+j}=d_{s+j}$ である。つまり $\dfrac{r_s}n$ と $\dfrac{r_{s+t}}n$ は、すべての位で数字が等しい。どちらも $0$ 以上 $1$ 未満なので、lem-rdf-remainder の 4 により $\dfrac{r_s}n=\dfrac{r_{s+t}}n$、すなわち $r_s=r_{s+t}$ である。$\square$

方針：$n+1$ 個の余り $r_0,r_1,\dots,r_n$ を、$n$ 通りの値に振り分ける（部屋割り論法）。
段 1。余り $r_0,r_1,\dots,r_n$ は $n+1$ 個あり、どれも $0,1,\dots,n-1$ の $n$ 通りの値のどれかである。$n+1$ 個を $n$ 通りに振り分けるので、同じ値のものが少なくとも 2 つある。それを $r_i=r_j$（$0\le i< j\le n$）とする。
段 2。$s=i$、$t=j-i$ とおくと $t\ge1$、$r_{s+t}=r_j=r_i=r_s$ である。prop-rdf-criterion により、$\dfrac an$ は $(s,t)$ で循環する。$s+t=j\le n$ である。$\square$

方針：cor-rdf-always を $\dfrac1m$ に使い、整数の割り算と互除法 の「互いに素な数による割り算」（$a\mid bc$ かつ $\gcd(a,b)=1$ なら $a\mid c$）で $10^s$ を取り除く。
段 1。$m=1$ なら、どの整数も $1$ で割り切れるので $k=1$ でよい。以下 $m\ge2$ とする。
段 2。cor-rdf-always を $\dfrac1m$（$a=1$、$n=m$）に使うと、$s+t\le m$、$t\ge1$ で $(s,t)$ で循環する組がある。prop-rdf-criterion により $r_{s+t}=r_s$ である。$r_k$ は $10^k$ を $m$ で割った余りなので、$10^{s+t}\equiv10^s\pmod m$、すなわち
$$ m\mid10^{s+t}-10^s=10^s(10^t-1) $$
である。
段 3。$10^s$ の素因数は $2$ と $5$ だけで、$m$ は $2$ でも $5$ でも割り切れないので、$m$ と $10^s$ に共通の素因数はなく、$\gcd(m,10^s)=1$ である。互いに素な数による割り算により $m\mid10^t-1$、すなわち $10^t\equiv1\pmod m$ である。$1\le t\le s+t\le m$ なので、$k=t$ でよい。$\square$

方針：$t$ を $d$ で割った余りを考え、余りが $d$ より小さいことと $d$ の最小性を比べる。
段 1。$t$ を $d$ で割って $t=qd+u$（$q\ge0$、$0\le u< d$）とする。$10^d\equiv1$ なので、合同式の計算規則（両辺の累乗・積をとってよい）により
$$ 10^t=\left(10^d\right)^q\cdot10^u\equiv1^q\cdot10^u=10^u\pmod m $$
である。
段 2（$d\mid t$ ならば $10^t\equiv1$）。$d\mid t$ なら $u=0$ なので、段 1 により $10^t\equiv10^0=1$ である。
段 3（$10^t\equiv1$ ならば $d\mid t$）。$10^t\equiv1$ なら、段 1 により $10^u\equiv1$ である。もし $u\ge1$ なら、$u$ は $10^u\equiv1$ をみたす正の整数で $u< d$ となり、$d$ が最小であることに反する。よって $u=0$、すなわち $d\mid t$ である。$\square$

方針：prop-rdf-criterion で「$(s,t)$ で循環する」を「$r_{s+t}=r_s$」に直し、それを $n\mid10^s(10^t-1)$ という割り切りの条件に直す。そのあと、$n$ を $2^\alpha5^\beta$ の部分と $m$ の部分に分けて調べる。以下、互いに素な数による割り算（整数の割り算と互除法。$A\mid BC$ かつ $\gcd(A,B)=1$ なら $A\mid C$）を何度も使う。
段 1（割り切りの条件に直す）。$r_k$ は $10^ka$ を $n$ で割った余りなので、$r_{s+t}=r_s$ は $10^{s+t}a\equiv10^sa\pmod n$、すなわち
$$ n\mid10^sa\,(10^t-1) $$
と同値である。$\gcd(a,n)=1$ なので、互いに素な数による割り算により、これは
$$ n\mid10^s(10^t-1) $$
と同値である（逆向きは、$10^s(10^t-1)$ の倍数 $10^sa(10^t-1)$ も $n$ で割り切れることから分かる）。prop-rdf-criterion とあわせると、$\dfrac an$ が $(s,t)$ で循環することは $n\mid10^s(10^t-1)$ と同値である。
段 2（$n$ を 2 つに分ける）。$N=10^s(10^t-1)$ とおく。$2^\alpha5^\beta$ と $m$ は共通の素因数をもたないので互いに素である。したがって、$n\mid N$ は「$2^\alpha5^\beta\mid N$ かつ $m\mid N$」と同値である。実際、$n\mid N$ ならこの 2 つは成り立つ。逆に 2 つが成り立てば、$N=2^\alpha5^\beta u$ と書けて、$m\mid2^\alpha5^\beta u$、$\gcd(m,2^\alpha5^\beta)=1$ から $m\mid u$ となり、$n=2^\alpha5^\beta m\mid N$ である。
段 3（$2^\alpha5^\beta$ の部分）。$10^t-1$ は一の位が $9$ なので、$2$ でも $5$ でも割り切れない。$s\ge\alpha$ かつ $s\ge\beta$ なら、$2^\alpha5^\beta$ は $2^s5^s=10^s$ を割るので $N$ も割る。逆に $2^\alpha5^\beta\mid N$ とする。$2^\alpha\mid N=2^s\cdot5^s(10^t-1)$ で、$5^s(10^t-1)$ は奇数なので $\gcd(2^\alpha,5^s(10^t-1))=1$ であり、$2^\alpha\mid2^s$、すなわち $\alpha\le s$ である。同じように $\beta\le s$ である。よって、$2^\alpha5^\beta\mid N$ は $s\ge s_0$ と同値である。
段 4（$m$ の部分）。$m$ は $2$ でも $5$ でも割り切れないので $\gcd(m,10^s)=1$ であり、$m\mid10^s(10^t-1)$ は $m\mid10^t-1$、すなわち $10^t\equiv1\pmod m$ と同値である。
段 5（2 の証明）。段 1〜4 により、$(s,t)$ で循環することは「$s\ge s_0$ かつ $10^t\equiv1\pmod m$」と同値である。$(s_0,t_0)$ はこの条件をみたすので、$\dfrac an$ は $(s_0,t_0)$ で循環する。循環する組の $s$ はすべて $s_0$ 以上なので、循環しない部分の長さは $s_0$ である。循環する組の $t$ はすべて $10^t\equiv1\pmod m$ をみたし、そのような $t$ の最小は $t_0$ なので（def-rdf-order）、循環節の長さは $t_0$ である。
段 6（1 の証明）。$m=1$ とする。$k\ge s_0$ なら $2^\alpha5^\beta=n$ が $10^k$ を割るので、$10^ka$ も $n$ で割り切れて $r_k=0$ である。lem-rdf-remainder の 2 により、小数第 $s_0+1$ 位から先の数字はすべて $\lfloor0/n\rfloor=0$ で、$\dfrac an$ は有限小数である。
逆に、$\dfrac an$ が有限小数で、小数第 $k+1$ 位から先の数字がすべて $0$ だとする。lem-rdf-remainder の 3 により $\dfrac{r_k}n$ の数字はすべて $0$ である。$0$ の数字もすべて $0$ なので、lem-rdf-remainder の 4 により $\dfrac{r_k}n=0$、つまり $r_k=0$ で、$n\mid10^ka$ である。$\gcd(a,n)=1$ から $n\mid10^k$ であり、$m\mid10^k$ である。$m$ は $10^k$ の素因数 $2,5$ をもたないので、$m=1$ である。$\square$

thm-rdf-main の 2 により、$\dfrac an$ が $(0,t)$ で循環するある $t$ があることは、$0\ge s_0=\max(\alpha,\beta)$、すなわち $\alpha=\beta=0$ と同値である。$\alpha=\beta=0$ は、$n$ が $2$ でも $5$ でも割り切れないことにほかならない。このとき $m=n$ なので、循環節の長さは $\operatorname{ord}_n(10)$ であり、$a$ によらない。$\square$

方針：$m$ と互いに素な余りの集合 $U=\{r\mid1\le r\le m-1,\ \gcd(r,m)=1\}$ を、$10$ を掛ける操作でできる輪に分ける。$U$ の要素の個数は $\varphi(m)$ である（$m\ge2$ では $m$ 自身は $m$ と互いに素でないので、$1$ 以上 $m-1$ 以下で数えればよい）。$d=\operatorname{ord}_m(10)$ とおく。
段 1（$10$ を掛けても $U$ から出ない）。$r\in U$ とし、$10r$ を $m$ で割った余りを $r'$ とする。$m$ の素因数 $p$ が $10r$ を割ったとすると、素数の性質（Euclid の補題）により $p\mid10$ または $p\mid r$ である。$p\mid10$ なら $p=2$ か $5$ で、$m$ が $2$ でも $5$ でも割り切れないことに反する。$p\mid r$ なら $\gcd(r,m)=1$ に反する。よって $\gcd(10r,m)=1$ である。$r'=10r-qm$（$q$ は商）なので、$r'$ と $m$ の公約数は $10r$ も割り、$\gcd(r',m)=\gcd(10r,m)=1$ である。$m\ge2$ なので $r'\ne0$ で、$r'\in U$ である。
段 2（1 つの輪には $d$ 個の異なる余りがある）。$r\in U$ に対し、$10^kr$ を $m$ で割った余りを $k=0,1,\dots,d-1$ について並べたものを、$r$ の輪 $C(r)$ とよぶ。これら $d$ 個は互いに異なる。実際、$0\le i< j\le d-1$ で $10^ir\equiv10^jr\pmod m$ とすると、$m\mid10^ir(10^{j-i}-1)$ である。$\gcd(m,10^ir)=1$（段 1 と同じ理由）なので $m\mid10^{j-i}-1$ となるが、$0< j-i< d$ なので $d$ の最小性（def-rdf-order）に反する。また $10^dr\equiv r$ なので、$d$ 個進むと $r$ に戻る。
段 3（2 つの輪は一致するか、共通部分がない）。$C(r)$ と $C(r')$ に共通の余り $u$ があるとし、$u\equiv10^ir\equiv10^jr'$（$0\le i,j\le d-1$）とする。$10^d\equiv1$ なので
$$ r'\equiv10^d\,r'=10^{d-j}\cdot10^jr'\equiv10^{d-j}\cdot10^ir=10^{d-j+i}r\pmod m $$
である。さらに、任意の $k\ge0$ について $10^kr'\equiv10^{k+d-j+i}r$ である。prop-rdf-order-divides の証明の段 1 と同じく、指数 $k+d-j+i$ を $d$ で割った余りを $e$ とすると $10^{k+d-j+i}r\equiv10^er$ で、これは $C(r)$ の余りである。よって $C(r')$ の余りはすべて $C(r)$ に入る。$C(r)$ も $C(r')$ も $d$ 個の余りからなるので、$C(r')=C(r)$ である。
段 4（数える）。$U$ のどの余り $r$ も、自分の輪 $C(r)$ に入っている（$k=0$）。段 3 により、異なる輪は共通部分をもたない。したがって $U$ は、共通部分のない $c$ 個の輪に分かれ、段 2 によりどの輪も $d$ 個の余りを含む。よって $\varphi(m)=cd$ であり、$d\mid\varphi(m)$ である。
段 5（素数の場合）。$p$ が $2,5$ 以外の素数なら、$1$ から $p-1$ までの整数はすべて $p$ と互いに素なので $\varphi(p)=p-1$ である。cor-rdf-pure により $\dfrac1p$ の循環節の長さは $\operatorname{ord}_p(10)$ で、これが $p-1$ を割る。$\square$

方針：$10^{s+t}x$ と $10^sx$ の小数部分が等しいことを示し、引き算で小数部分を消す。
段 1（整数部分の計算）。def-rdf-digit の式 $\lfloor10^ix\rfloor=10\lfloor10^{i-1}x\rfloor+d_i$ を $i=s+1,\dots,s+t$ の順に使うと、
$$ \lfloor10^{s+t}x\rfloor=10^t\lfloor10^sx\rfloor+\left(d_{s+1}10^{t-1}+d_{s+2}10^{t-2}+\cdots+d_{s+t}\right)=10^tA+B $$
である。同じ式を $i=1,\dots,s$ に使うと $\lfloor x\rfloor=0$ から $\lfloor10^sx\rfloor=d_110^{s-1}+\cdots+d_s$ となり、$A$ は数字 $d_1\cdots d_s$ を並べた整数である。
段 2（小数部分が等しい）。$k\ge0$ について $y_k=10^kx-\lfloor10^kx\rfloor$（$10^kx$ の小数部分）とおく。$0\le y_k<1$ である。prf-rdf-remainder の段 3 の計算は、$q_k=\lfloor10^kx\rfloor$ が整数であることしか使っていないので、そのまま成り立ち、$y_k$ の小数第 $j$ 位の数字は $d_{k+j}$ である。$(s,t)$ で循環するので、$j\ge1$ について $d_{s+t+j}=d_{s+j}$ であり、$y_{s+t}$ と $y_s$ はすべての位で数字が等しい。lem-rdf-remainder の 4 により $y_{s+t}=y_s$ である。
段 3（引き算）。段 2 により
$$ 10^{s+t}x-10^sx=\lfloor10^{s+t}x\rfloor-\lfloor10^sx\rfloor=(10^tA+B)-A=(10^t-1)A+B $$
である。左辺は $10^s(10^t-1)x$ で、$10^s(10^t-1)\ne0$ なので、両辺をこれで割れば主張の式を得る。分子と分母は整数なので $x$ は有理数である。$\square$

方針：筆算の余りを、最初の余り $1$ に戻るまで計算する（prop-rdf-criterion）。分母は $2$ でも $5$ でも割り切れないので、純循環小数である（cor-rdf-pure）。
(1) 余りは $1\to10\to18\to16\to37\to1$ である（$100=41\cdot2+18$、$180=41\cdot4+16$、$160=41\cdot3+37$、$370=41\cdot9+1$）。$5$ 回目で初めて $1$ に戻るので、長さは $5$ である。確かめとして、$99999=41\cdot2439$ なので $\dfrac1{41}=\dfrac{2439}{99999}=0.\overline{02439}$ である。
(2) 余りは $1\to10\to15\to14\to4\to6\to9\to5\to16\to7\to2\to3\to13\to11\to8\to12\to1$ であり（ex-rdf-always の 2）、$16$ 回目で初めて $1$ に戻る。長さは $16$ である。$\square$