SNNN数の周期
出典
Definition (informal)
一般化SNNN数$ Sと整数$ zに対し, 正整数$ uが$ m\equiv n\pmod u\implies S(m)\equiv S(n)\pmod zを満たすならば, $ uは$ zを法とする$ Sの周期という. $ zを法とする周期のうち最小のものを基本周期といい, $ u_zで表す. もう形式化はされているに等しいが, 一応論理式への翻訳だけやっておく:
Definition (formal)
$ \forall a, b, s, u, z\in\mathbb{Z}. $ 0\lt u.
1. $ uは$ zを法とする$ S_{a, b, s}の周期 :⇔ $ m\equiv n\pmod u\implies S_{a, b, s}(m)\equiv S_{a, b, s}(n)\pmod z.
2. $ \min\lbrace\,u\mid u\text{は}z\text{を法とする}S_{a, b, s}\text{の周期}\,\rbraceが存在するとき, これを基本周期といい, $ u_zで表す.
最小性より, 基本周期は存在すれば唯一である.
基本性質
以下, 一般化SNNN数に付随して定義される写像$ f\colon \mathbb{Z}\to \mathbb{Z}を記号として固定する.
Thm. 1 (formal)
$ \forall a, b, s\in\mathbb{Z}. $ \forall z, m, n\in\mathbb{N}. $ \forall u_z\in\mathbb{N}\setminus\lbrace\,0\,\rbrace. $ u_zが$ zを法とする$ S_{a, b, s}の基本周期であるならば, 次は同値.
1. $ m\equiv n\pmod {u_z}.
2. $ S_{a, b, s}(m)\equiv S_{a, b, s}(n)\pmod z.
Proof
(1.) ⇒ (2.)
定義より明白
(2.) ⇒ (1.)
$ (m', n') := (m\bmod u_q, n\bmod u_q). 一般性を失わず$ m'\lt n'を仮定してよい.
$ m\equiv m' \pmod {u_z}, $ n\equiv n' \pmod {u_z}なので定義より$ S_{a, b, s}(m)\equiv S_{a, b, s}(m')\pmod zかつ$ S_{a, b, s}(n)\equiv S_{a, b, s}(n')\pmod z. よって$ S_{a, b, s}(m)\equiv S_{a, b, s}(n)\pmod z\implies S_{a, b, s}(m')\equiv S_{a, b, s}(n')\pmod z.
仮定より左辺は成立するため右辺も成立.
すると次が成立する.
$ \begin{aligned}S_{a, b, s}(m')\equiv S_{a, b, s}(n')\pmod z &\iff f^{m'}(s)\equiv f^{n'}(s)\pmod z\cr &\iff f^{u_z - n'}(f^{m'}(s))\equiv f^{u_z - n'}(f^{n'}(s))\pmod z\cr&\iff f^{m'-n'}(f^{u_z}(s))\equiv f^{u_z}(s)\pmod z\cr&\iff f^{m'-n'}(s)\equiv s\pmod z\cr&\iff S_{a, b, s}(m'-n')\equiv S_{a, b, s}(0)\pmod z\end{aligned}
Lem. Aより$ m'-n'は周期.
Lem. Bより$ u_z\mid (m' - n')なので$ m'\equiv n'\pmod {u_z}.
$ m\equiv m' \pmod {u_z}, $ n\equiv n' \pmod {u_z}であったことを思い出すと$ m\equiv n\pmod {u_z}が結論される. $ \Box
Lem. A (formal)
$ \forall a, b, s\in\mathbb{Z}. $ \forall z\in\mathbb{N}. $ \forall u\in\mathbb{N}\setminus\lbrace\,0\,\rbrace. $ uが$ zを法とする$ S_{a, b, c}の周期であるための必要十分条件は $ S_{a, b, s}(u)\equiv S(0)\pmod z.
Proof
必要性
定義より明白
十分性
$ f^u(s) \equiv f^0(s) \equiv s \pmod {z}である.
$ \forall n, m\in\mathbb{N}. $ n \equiv m\pmod{u}. とするとき$ \exists k\in\mathbb{Z}. $ n = m + uk. これゆえ$ S_{a, b, s}(n)\equiv f^n(s) = f^m(f^{uk}(s))\equiv f^m(s)\equiv S_{a, b, s}(m)\pmod z. $ \Box
Lem. B (formal)
$ \forall a, b, s\in\mathbb{Z}. $ \forall z\in\mathbb{N}. $ \forall u_z\in\mathbb{N}\setminus\lbrace\,0\,\rbrace. $ u_zが$ zを法とした$ S_{a, b, s}の周期であるならば, 以下は同値.
1. $ u_zは$ zを法とした$ S_{a, b, s}の基本周期である.
2. $ \forall u\in\mathbb{N}\setminus\lbrace\,0\,\rbrace. $ uが$ zを法とする$ S_{a, b, s}の周期であるならば$ u_z\mid u.
Proof.
(1.) ⇒ (2.).
除法の原理より$ \exists!q, r\in\mathbb{Z}. $ u = u_zq+r\land 0\leq r\lt u_z.
$ \forall m, n\in\mathbb{N}. $ m - n\equiv 0\pmod uより$ \exists k\in\mathbb{Z}. $ m - n = uk = u_zqk + rk.
特に$ k\mid (m - n)より$ (m - n) / k\in\mathbb{Z}かつ$ u\mid (m-n)/kである.
$ uは周期だから$ S((m - n)/k) \equiv S(0)\pmod z. 同時に$ S((m - n)/k)\equiv S(u_zq+r) \equiv f^{r}((f^{u_z})^{q}(s))\equiv S(r)\pmod z.
Lem. Aより$ rも周期. 一方$ 0\leq r\lt u_zかつ$ u_zの最小性より$ r = 0でなければならない.
したがって$ u_z\mid u.
(2.) ⇒ (1.).
$ Xを$ zを法とした$ S_{a, b, s}の周期の全体とする. $ u_z\in Xより$ X\neq\emptyset, かつ$ X\subseteq\mathbb{N}より$ \min Xが存在する. $ v := \min Xとおく. $ vは最小性から基本周期である.
(2.)より$ u_z\mid vである.
$ vは基本周期だから, (1.) ⇒ (2.)より$ v\mid u_z.
よって$ u_zと$ vは単数の差である ($ \mathbb{Z}はEuclid整域なのでUFD. UFDにおいて同伴な2元は単数の差. ). $ \mathbb{Z}の単数は1, -1であり, $ \lbrace\,u_z, v\,\rbrace\subsetneq \mathbb{N}であるから, $ u_z = v. $ \Box