倍数法則の存在に関する必要十分条件

SNNN数の巡回定理では基本周期の考え方をもとに倍数法則の値を具体的に算出しているが, 具体性を多少失ってよいのであれば別視点から必要十分条件を与えられる. 本命題はこの立場のもとで一般に解決するものである.

Statement (formal)

$ \forall M, k\in\mathbb{N}. $ \gcd(M, 102) = 1. とする. 次の2つは互いに同値.

1. $ 7/34\equiv 10^k\pmod M.

2. $ \forall n\in\mathbb{N}. $ \lbrack\exists\ell\in\mathbb{N}.\ n = \mathrm{o}(10)\ell+k \iff M\mid S(n)\rbrack.

ただし$ \mathrm{o}(10)は$ (\mathbb{Z}/M\mathbb{Z})^\timesにおける$ 10の位数を表す.

Proof

(1.) ⇒ (2.)

$ \Longrightarrow:

$ \begin{aligned} S(o(10)\ell+k)&\equiv (34\cdot 10^{o(10)\ell+k}-7)/9\cr &\equiv (34\cdot 10^k-7)/9\cr&\equiv (34\cdot 7/34-7)/9\cr &\equiv 0\pmod M \end{aligned}

$ \Longleftarrow: $ S(n)\equiv (34\cdot 10^n-7)/9\pmod Mかつ$ S(n)\equiv 0\pmod Mより$ 10^n\equiv 7/34\pmod M. $ 10^{n - k}\equiv 1\pmod Mより$ \exists \ell\in\mathbb{N}.\ n - k = o(10)\ell. $ \Box

(2.) ⇒ (1.)

$ n = kとおいたとき$ n = o(10)\cdot 0 + kだから$ M\mid S(k). $ S(k)\equiv 0\pmod Mより次が成立.

$ \begin{aligned} S(k)\equiv 0 &\iff (34\cdot 10^k - 7) / 9 \equiv 0\cr&\iff 10^k\equiv 7/34\pmod M \end{aligned}

よって成立. $ \Box

Note

離散対数$ kは常に存在するとは限らない

存在しない場合, その素数はいかなるSNNN数をも割り切らない

存在条件を検討するには $ (\mathbb{Z}/M\mathbb{Z})^\timesの部分群の束構造を具体的に決定することを考えなければならない

有限アーベル群の構造定理で分解した先の単因子で議論すればよい

単因子が1つしかないなら離散対数は常に存在する → $ p = 9551の場合存在しないというか素数位数なら全部巡回群になるから反例は無限に構成できる ($ p = 9520k + 31ref. 全てのSNNN数を割り切らない素数 (SNNN数論))

$ (7/34)^{20}\equiv 10\pmod {9551}

先の構成法にない例として$ p = 10009の場合も任意のSNNN数により割り切れない

$ (7/34)^{9362}\equiv 10\pmod {10009}

単純に$ \mathrm{o}(7/34)\lt \mathrm{o}(10)かどうかだけが問題?

code:experiments.gp

p = 10007

p = 10009

p = 9551

g = znprimroot(p)

x = Mod(10, p)

y = Mod(7/34, p)

a = znlog(x, g)

znorder(y) < znorder(x), znlog(y, x), znlog(x, y), y^((p-1) / gcd((p-1), a))

10と7/34の位数が互いに素である場合は確実に割り切らない

7/34のn冪剰余が存在する場合10べきに帰着できるように見えているが, 未証明

n冪剰余に関する検討

TODO: 一般化SNNN数への一般化

$ kの一意性は言わなくてよい? 言えるけどどう組み込む?

SNNN素数として判明している0, 1, 11, 17, 773について, その添字は以下の一般項により表される

$ S(0) = 3: $ 3x

$ S(1) = 37: $ 3x + 1

$ S(11) = 377777777777: $ 377777777776x + 11

$ S(17) = 377777777777777777: $ 377777777777777776x + 17

$ S(773): $ (S(773) - 1)x + 773

大きすぎて位数や離散対数の直接計算は難しいが, Mod(7/34, S773) == Mod(10, S773)^773 であることはすぐ確認できることから離散対数については773でよい. 位数はPRPであることから仮定しているので不正確やもしれない.

このとき, 各一般項は一切の共通根をもたない. 実際, resultantを互いに取って0となるようなものは皆無である.

SNNN素数以外でも起こる現象には見えているが, どの程度素数性が影響しているのかは不明

Code

code:multiply_theorem.gp

M = 自然数

a = znorder(Mod(10, M))

k = znlog(Mod(7/34, M), Mod(10, M))

a * 'l + k

#命題 #倍数法則