---
tags: 数学, 整数問題
---
今年の整数問題（2019/01/10）
==================

## 問題

### 【問題1】

$\frac{n}{35530n+1}$ を十進小数表記したとき循環節の長さ（最小のもの）が $n$ となる最小の整数 $n(\ge 1)$ を求めよ。ただし今日(2019/01/10)は私の $n$ 歳の誕生日です。

### 【問題2】

問題1 の解を $n_0$ とおく。問題1 の題意を満たす $n > n_0$ について論じよ。もし存在すれば例を示せ、存在しないならそれを証明せよ。

## 解答

【問題1】
$n = 43$

【問題2】
例えば $n = 374011, 10061599$ 等は題意を満たす。

### 解説

#### 定義・前提条件等

有理数（$0<r<1$）を（十進）小数展開したときに循環小数となり、ある数字列 $a_i, b_j\ (0 \le a_i, b_j \le 9)$ を用いて「$0.a_1a_2\dots a_l\ b_1b_2\dots b_k\ b_1b_2\dots b_k\ \dots$」のように書けるとする。
**循環節** とはこの「$b_1b_2\dots b_k$」の部分を指す言葉とする、すなわち数字列の繰り返し単位を指す言葉とする。
例えば $\frac{4}{33} = 0.12121212\dots$ の場合は 「$12$」も「$1212$」も「$12121212$」も循環節であるが、そのうち長さが最小のもの（この場合「$12$」）を **基本循環節** と呼ぶ。
これ以降、特に断りがない限り、基本循環節の意味で『循環節』という言葉を用い、「基本循環節の長さ（＝循環節の長さのうち最小のもの）」のことを指して『**循環節の長さ**』という言葉を用いる。

なおこの記事の数学的背景は、主に 参考文献1[^1] に依っている。

#### 【問題1】

まず、以下の2つの命題を考える：

:::info
### ==命題1.==

$m > 1$ を $\gcd(m, 10) = 1$ とし、$\frac{1}{m}$ の循環節の長さを $k$ とおく。この時、$10^k \equiv 1 \ ({\rm mod}\ m)$ である。
:::

> 註：この命題における循環節（の長さ）は基本循環節（の長さ）に限らず、一般に成立する。
>
> 証明：
>
> 一般に、小数点以下の循環節の前までを $l$ 桁とすると、ある整数 $a\ (0 \le a < 10^l), b\ (1 \le b < 10^k)$ が存在して以下が成り立つ：
>
> $$
\begin{eqnarray*}
\frac{1}{m} &=& \frac{a}{10^l} + \frac{b}{10^{k+l}} + \frac{b}{10^{2k+l}} + \dots \\
&=& \frac{a}{10^l} + \frac{b}{10^l} \cdot \frac{\frac{1}{10^k}}{1 - \frac{1}{10^k}}\\
&=& \frac{a}{10^l} + \frac{b}{10^l} \cdot \frac{1}{10^k - 1}\\
&=& \frac{a(10^k-1) + b}{10^l(10^k - 1)}
\end{eqnarray*}
$$
>
> 特に $m \mid 10^l(10^k-1)$ である。
> ここで $\gcd(m, 10) = 1$ より、$m \mid 10^k-1$、すなわち $10^k \equiv 1 \ ({\rm mod}\ m)$ である。
>
> （証明終わり）
>
> 補足：この時、実際には $l=0$、$a=0$ すなわち $\frac{1}{m} = \frac{b}{10^k-1}$ となる（参考文献1[^1] の定理1・定理2 参照） 。

[^1]: 参考文献1：[循環小数についての種々の考察](http://www2r.biglobe.ne.jp/kosanhp/math/junkan.pdf)（2008年 5月　奥村 清志）

:::info
### ==命題2.==

$m > n > 1$ を $\gcd(m, 10) = 1, \gcd(m, n) = 1$ とし、$\frac{1}{m}$ の循環節の長さを $k$ とおく。この時、$\frac{n}{m}$ の循環節の長さも $k$ である。
:::

> 証明：略（参考文献1[^1] の「3 シフト系とその性質 (その 1)」以降を参照）

$n \in \mathbb{Z}_{>0}$ に対して $\gcd(35530n + 1, 10) = 1$ かつ $\gcd(35530n + 1, n) = 1$ なので、==命題1.== と ==命題2.== より、$\frac{n}{35530n + 1}$ の循環節の長さが $n$ となるかどうかは、$35530n + 1$ で $10^n$ を割った余りが $1$ になるかどうか（かつ、任意の整数 $n^\prime$（$1 \le n^\prime < n$）について $35530n + 1$ で $10^{n^\prime}$ を割った余りが $1$ とならないかどうか）を見れば良い。

簡単なプログラムを書くことによって、そのような $n$ の最小値が $n_0 = 43$ であることは容易に確かめられる。以下はそのようなプログラム例（言語：[Julia](https://julialang.org)）である。`powermod(b, k, m)` は「$b^k$ を $m$ で割った余り（累乗剰余）」を計算する関数である。答えは一瞬で返ってくる

function solve1()
    for n = 2:100
        den = 35530n + 1
        if powermod(10, n, den) == 1
            all(powermod(10, k, den) != 1 for k=2:n-1 if n%k==0) && return n
        end
    end
end

#### 【問題2】

問題1の解答 $n_0 = 43$ について考えると、それ自身も $35530n_0+1 = 1527791$ も素数であることが分かる。
実際、$\frac{1}{an+1}$ の循環節の長さが $n$ となるなら、$n$ も $an+1$ も素数であることが多い。

> ∵ $\phi(n)$ をオイラーの関数（$n \in \mathbb{Z}_{>0}$ に対して $n$ と互いに素な整数 $k (1 \le k < n)$ の個数を返す関数）とすると、$\frac{1}{n}$ の循環節の長さは $\phi(n)$ の約数であることが知られている。
> 素数 $p$ に対しては $\phi(p)=p-1$ なので、$an+1$ が素数なら $\phi(an+1) = an$ である。よって $\frac{1}{an+1}$ の循環節の長さは $an$ の約数と言うことになり、$n$ となる可能性が高くなる。
> また $n$ が素数ならば、任意の $k\ (1 < k < n)$ に対して $10^k-1$ は $10^n-1$ の約数にならない（k が n の約数になり得ないので）。これは $\frac{1}{an+1}$ の循環節の長さ（の候補）が $n$ であると分かった場合に、その約数（$<n$）となる可能性がないことを意味する。よって $an+1$ が $10^n-1$ を割り切るかどうかだけを確認すれば良い。

よって $43$ より大きな素数 $p$ を考えて、$35530p+1$ も素数となるものについてそれが $10^p-1$ を割り切るかどうかを確認する、と言う方法で比較的効率的に候補を探すことが出来る。

この方法で求解するプログラム例を示す（言語：Julia、要 [Primes.jl](https://github.com/JuliaMath/Primes.jl)）：

using Primes

function find_answer_over_43()
    lo = 43
    hi = 35530
    while true
        for p in primes(lo + 1, hi)
            den = 35530p + 1
            if isprime(den)
                if powermod(10, p, den) == 1
                    @debug "Found!" p
                    return p
                else
                    @debug "NG" p
                end
            else
                @debug "Pass…" p
            end
        end
        lo = hi
        hi += 30000
    end
end

（`@debug` はデバッグログ出力のためのマクロで、通常は何も出力されない。`ENV["JULIA_DEBUG"] = "all"` 等の設定がしてあれば然るべき出力先（デフォルトでは標準エラー出力）にデバッグ情報が出力される）

これを実行することで、数秒程度で $n = 10061599$ が見つかる。$35530 \times 10061599 + 1 = 357488612471$ であり、$\frac{1}{357488612471}$ の循環節の長さは $10061599$ となる（確認は読者への宿題とするw）。

これが題意を満たす整数のうち $43$ の次に小さい数かというと、これよりも小さいものが存在することも容易に確認できる。

using Primes

function generate_answers(;lo=2, hi=200000000000000)
    Channel(ctype=Int, csize=1) do channel::Channel{Int}
        for n::Int = lo:hi
            den = 35530n + 1
            if powermod(10, n, den) == 1
                if isprime(n)
                    put!(channel, n)
                elseif all(powermod(10, k, den) != 1 for k=2:n-1 if n%k==0)
                    put!(channel, n)
                else
                    @debug "NG" n
                end
                yield()
            end
        end
    end
end

（`Channel` は Julia の`Task`（コルーチン）間でデータをやり取りできるオブジェクト（go言語の `channel` に相当））

このプログラムは $n \ (2 \le n \le 200000000000000)$ に対して題意を満たすものを全て列挙するものである（`Int == Int64` を仮定している）。関数の戻り値は `Channel{Int}` であり、これを `for` 文に渡したり `Iterators.take()` を利用することで最初の数件を取り出したり出来る。例えば以下のようにすると、数十秒程度で $43$〜$10061599$ までの最初の21件を列挙する。

for (i,n) in enumerate(generate_answers())
     println("$i: $n")
     n >= 10061599 && break
end
# => 1: 43
#    2: 374011
#    3: 383880
#    4: 430387
#    5: 498279
#    6: 874252
#    7: 991020
#    8: 1898659
#    9: 2233080
#    10: 3166507
#    11: 4455471
#    12: 5371759
#    13: 5774791
#    14: 6229056
#    15: 7008067
#    16: 7743076
#    17: 7787292
#    18: 8442591
#    19: 8505576
#    20: 9864931
#    21: 10061599

これにより、題意を満たす $43$ の次に小さいものは $n_1 = 374011$ であることが分かる。それ自身は素数ではない（$374011 = 11^3 \cdot 281$）が、$35530n_1 + 1 = 13288610831$ は素数である。

なお今のところ、$1 \le n \le 4294967295$（$4294967295 = 2^{32}-1$ は32bit符号なし整数の最大値）までの題意を満たす $n$ で、$35530n+1$ が素数でないものは見つかっていない。

（終わり）