A(n)は、
(10e - 1) / 9 ≡ 0 (mod n)
となる1以上で最小のeです。
nが2または5で割り切れるとき、この式を満たすeは無いので考慮に入れません。
A(n)は、nが3で割り切れないとき、
10e ≡ 1 (mod n)
となる最小のeです。7の剰余なら、10から10倍していって、
10 → 2 → 6 → 4 → 5 → 1
だから最小のeは6、11の剰余なら、
10 → 1
だから2です。このeをB(n)と書くことにしましょう。B(7) = 6、B(11) = 2です。
nの既約剰余類群で10が原始根になっていればB(n) = φ(n)です。既約剰余類というのは、nと互いに素の剰余の乗法に関する群です。例えばn = 12なら、1, 5, 7, 11がnに互いに素です。そうするとこれが乗法に関して群になります。
| 1 | 5 | 7 | 11 | |
|---|---|---|---|---|
| 1 | 1 | 5 | 7 | 11 |
| 5 | 5 | 1 | 11 | 7 |
| 7 | 7 | 11 | 1 | 5 |
| 11 | 11 | 7 | 5 | 1 |
この群の元はオイラーの関数を使ってφ(n)個あります。geで全ての元を生成できるとき、gを原始根と言います。そのとき全ての元をめぐって1周してくるので、gφ(n) ≡ 1となってφ(n)がge ≡ 1を満たす最も小さいeです。
nが素数pのとき、原始根は必ず存在します。このときφ(p) = p - 1なので、B(p) = p - 1です。だから、pが小さくてもB(p)が比較的大きくなります。これ以外で大きくなるのはn = p2と書けるときです。φ(n) = p(p - 1)です。これがNを超えると、p > √N + 1/2なので、n > N + √Nです。N = 106なら、nはNを1000以上超えることになります。一方、NとN + √Nの間には素数定理から√N / logN ≒ 72個くらいあります。nが素数のとき必ずしも10が原始根になるわけではないですが、原始根は各素数pに対してφ(p - 1)個あるので、10が原始根になる確率はそんなに低くないです。だから、NとN + √Nの間に10が原始根になる素数pがほぼ確実にあると言っていいでしょう。だから、nは素数だけを考えればよいです。
さて、素数pの既約剰余類について10が原始根であるか判定しましょう。例えば、p = 1801を考えます。p - 1 = 23 * 32 * 52です。読みにくいのでこれを指数だけ取り出して(3, 2, 2)と書くことにします。フェルマーの小定理から、
10p-1 ≡ 1(mod p)
だから、B(p)はp - 1に約数になります。そして、B(p)は(3, 2, 2)でないなら
(2, 2, 2), (3, 1, 2), (3, 2, 1)
のいずれかの約数になります。よってこの3つの自然数miについて、
10mi ≡ 1(mod p)
がいずれも成り立たなければ、p - 1の真約数のいずれでも成り立たないことになり、10が原始根であることがわかります。逆は明らかですね。さらに
10p-1 ≡ 1(mod p)
を判定に入れると素数判定をしなくても済みます。これを先に行うとある程度弾けるので、速度アップにつながります。
nが3を含む場合は、
(10e - 1) / 9 ≡ 0(mod n)
10e ≡ 1(mod 9n)
となります。n = 3em（mは3で割り切れない自然数）として、B(9n) = lcm(B(3e+2), B(m))となります。よってB(3e+2)を計算すればよいです。
101 ≡ 1(mod 9)
103 ≡ 1(mod 27)
から想像できるように、
B(3e+2) = e
となります。すなわち、103e = 3e+2d + 1（e ≥ 0、dは3で割り切れない自然数）となります。数学的帰納法でこれを証明しましょう。e = 0では上で見たように成り立ちます。e(≥ 0)で成り立つとすると、
103e+1 = (103e)3 = (3e+2d + 1)3 = 33e+6d3 + 32e+5d2 + 3e+3d + 1
= 3e+3d1 + 1（dは3で割り切れない自然数）
が成り立ちます。
よって、
B(9n) = B(3e+2m) = lcm(3e, B(m))
です。B(m)が3で割り切れず、かつm - 1のとき、
B(9n) = 3e(m - 1) = n - 3e
となります。これはeが小さければnに非常に近くなります。3で割り切れないときの素数で10が原始根のときとこれ以外のときは無視して計算します。
106のときは一瞬、1017で19秒でした。
