※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。


Problem 129 「レピュニットの非整除性」 †

1のみからなる数をレピュニットという. R(k) を長さ k のレピュニットとする. 例えば, R(6) = 111111 となる.

GCD(n, 10) = 1 なる正の整数 n が与えられたとき, R(k) が n で割り切られるような k が常に存在することが示せる. A(n) をそのような k の最小のものとする. 例えば, A(7) = 6, A(41) = 5 となる.

A(n) の値が10を超える最小の n は17である.

A(n) の値が100万を超える最小の n を求めよ


解法
111、、、111を9倍すると999、、、9999.
10^t-1=999、、、999
オイラーの定理より
10^φ(n) mod n=1
φ(n)の約数が候補になる。
nで割れる最小の長さの111、、111を9倍しても一桁大きい111、、111を超えない。

そして100万を超えた最初の素数nはφ(n)の約数はn-1のみでいきなり100万以上を満たす。
よって100万より大きい最初の素数が答え。