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万より大きい最初の素数が答え。
最終更新:2014年03月09日 06:20