循環小数の循環節の長さ
本文
問題提起
筆者が中学生か高校生のころ、有理数の小数表現、とくに循環節に何らかの規則性があるのではと調べてみたものの、よくわからず断念しました。
あれから時を経て、次のプログラミングの問題を目にしました。
これはまさに当時の疑問を解決してくれるものでした。
本稿ではこの問題の解法について解説します。
$N$を正の整数とする。
$\dfrac{1}{N}$を循環小数で表したときの循環節の長さを求めよ。
$O(1)$の陽関数として解が求められる問題ではないのですが、プログラミングを活用することで、ある程度は高速に求められるということです。
実験
小さい$N$に対して実験してみましょう。
割り切れる場合の循環節の長さは、$1=0.\dot{9}$と考えることにより、ここでは$1$とします。
| $N$ | $1/N$ | 循環節の長さ | 備考 |
|---|---|---|---|
| $1$ | $1$ | $1$ | 割り切れる |
| $2$ | $0.5$ | $1$ | 割り切れる |
| $3$ | $0.\dot{3}$ | $1$ | |
| $4$ | $0.25$ | $1$ | 割り切れる |
| $5$ | $0.2$ | $1$ | 割り切れる |
| $6$ | $0.1\dot{6}$ | $1$ | $N=3$と同じ |
| $7$ | $0.\dot{1}4285\dot{7}$ | $6$ | |
| $8$ | $0.125$ | $1$ | 割り切れる |
| $9$ | $0.\dot{1}$ | $1$ | |
| $10$ | $0.1$ | $1$ | 割り切れる |
| $11$ | $0.\dot{0}\dot{9}$ | $2$ | |
| $12$ | $0.08\dot{3}$ | $1$ | $N=3$と同じ |
| $13$ | $0.\dot{0}7692\dot{3}$ | $6$ | |
| $14$ | $0.0\dot{7}1428\dot{5}$ | $6$ | $N=7$と同じ |
| $15$ | $0.0\dot{6}$ | $1$ | $N=3$と同じ |
| $16$ | $0.0625$ | $1$ | 割り切れる |
| $17$ | $0.\dot{0}58823529411764\dot{7}$ | $16$ | |
| $18$ | $0.0\dot{5}$ | $1$ | $N=9$と同じ |
| $19$ | $0.\dot{0}5263157894736842\dot{1}$ | $18$ | |
| $20$ | $0.05$ | $1$ | 割り切れる |
| $21$ | $0.\dot{0}4761\dot{9}$ | $6$ |
この表を観察すると、次のことが予想できます。
- $2$ および $5$ では必ず割り切れるため、これらの素因数をはじめに取り除いて考えても循環節には影響しない
- $N$が素数のときに$N-1$となるようにも見えるが、反例がある ($N=3,11,13$)
- 循環する部分が一つ見つかったとすれば、循環節の長さはその約数
上で計算した$\dfrac{1}{N}$に$N$を掛けて戻すと、確かに$0.\dot{9}$となっています。
例えば、$N=7$のとき$142857 \times 7 = 999999$であり、
$10^k-1$が$N$で割り切れるような最小の$k$を求めることになります。
これは、
$$
~~ 10^k \equiv 1 \pmod N
$$
を満たす最小の$k$と言い換えられます。
準備
本問を解くのに必要な定理を準備します。
有名な定理については、証明は省略します。
$a$と$n$が互いに素であるとき、
$a^k \equiv 1 \pmod{n}$を満たす最小の$k>0$を、$a$の$\bmod n$ における位数 (order) と呼ぶ。
$a$と$n$が互いに素であり、$m$を$a$の$\bmod n$ における位数とするとき、
$$ ~~ k>0, ~ a^k \equiv 1 \pmod{n} ~\Longrightarrow~ m \mid k $$
$k=qm+r ~~ (0 \leq r < m)$とすると、$a^{qm+r} \equiv a^r \equiv 1$となるから、$r=0$。
$n$は正の整数とする。
$n$個の整数$1, 2, \cdots, n$のうち、$n$と互いに素なものの個数を
Euler の totient 関数
と呼び、$\varphi(n)$で表す。
$n$の素因数の種類 (重複なし) が $p_1, p_2, \cdots , p_m$ と表せたとすると、
$$ ~~ \varphi(n) = n \prod_{1 \leq i \leq m} \frac{p_i - 1}{p_i} $$
$a$と$n$が互いに素であるとき、
$$ ~~ a^{\varphi(n)} \equiv 1 \pmod{n} $$
今回は$N$が素数とは限らないため、 Fermat の小定理 を拡張した Euler の定理 を使います。
$a$と$n$が互いに素であり、$m$を$a$の$\bmod n$ における位数とするとき、
$$ ~~ m \mid \varphi(n) $$
定理 1 と定理 3 による。
解 (アルゴリズム)
$N$が$2$または$5$の倍数のとき、循環節の長さに影響しないため、$N$を$2$または$5$で割っておく。
ここで$N=1$となる場合、解は$1$とする。
以下、$10$と$N$は互いに素であるとする。
$\dfrac{1}{N}$に循環する部分があるとすると、それはある長さ$k>0$の$999 \cdots 9$を$N$で割ったものである。
すなわち、
$$ ~~ 10^k-1 \equiv 0 \pmod{N} $$
$$ ~~ 10^k \equiv 1 \pmod{N} $$
求める循環節の長さは、上の式を満たす最小の$k>0$である。
$10$と$N$は互いに素であるから、求める循環節の長さは$10$の$\bmod N$ における位数となり、
定理 4 より、これは$\varphi(N)$の約数のいずれかである。
したがって、$\varphi(N)$の約数$d$を小さい順に列挙し、$10^d \equiv 1$を満たしていればそれが解となる。
$10^{\varphi(N)} \equiv 1$であるため、解は必ず存在する。
なお、$10^1 \equiv 1 \pmod{1}$を満たすため、この議論は$N=1$でも成り立つ。
時間計算量は、$\varphi(N)$の計算およびその約数の列挙の部分がともにボトルネックとなり、$O( \sqrt{N} )$となります。
補記
解法としては上記で十分ですが、Euler の定理における$\varphi(n)$をさらに精緻化した
Carmichael の定理
があり、
$a$と$n$が互いに素であるとき、「すべての$a$に対して$a^k \equiv 1 \pmod{n}$を満たす$k>0$」の最小値として、Carmichael 関数$\lambda(n)$が求められます。
ただし、特定の$a=10$に対して最小になるとは限らないため、解は$\lambda(n)$の約数のいずれかであるという点は変わりません。
したがって、次の結果が得られます。
$10$と$n$が互いに素であるとき、
$\dfrac{1}{n}$を循環小数で表したときの循環節の長さは$10^k \equiv 1 \pmod{n}$を満たす最小の$k>0$であり、
それは$\lambda(n)$の約数のいずれかである。
また、本稿に現れた循環小数の性質は、全ての桁の数字が$1$である レピュニット (レプユニット; repunit) とも関連があります。
$n$を正の整数とする。
ある長さ$k>0$のレピュニット$R_k$が存在して$n \mid R_k$を満たすならば、
$3n \mid R_{3k}$が成り立つ。
$n \mid R_k$であるとする。
$$ ~~ R_{3k} = R_k \cdot 10^{2k} + R_k \cdot 10^k + R_k = R_k (10^{2k} + 10^k + 1) $$
ここで、$10^{2k} + 10^k + 1 = 100 \cdots 00100 \cdots 001$は$3$の倍数だから、$3n \mid R_{3k}$が成り立つ。
$10$と$n$が互いに素であるとき、
ある長さ$k>0$のレピュニット$R_k$が存在して、$n \mid R_k$を満たす。
上の解についての議論から、
$$ ~~ 10^k-1 \equiv 0 \pmod{n} $$
を満たす$k>0$が存在する。
すなわち、この$k$に対して$n \mid 9R_k$を満たす。
(i) $3$と$n$が互いに素であるとき、$n \mid R_k$を満たす ($n=1$を含む)。
(ii) $3$と$n$が互いに素でないとき、補題 6 および (i) により、再帰的に題意が成り立つ。