【定理】
整数係数多項式 に対し,整数列
を
,
と定義する.
が任意の自然数
について
上で周期
をもつための必要十分条件は,
かつ
.
[補題1]
が
上で周期
をもつための必要十分条件は,
かつ
.
[補題1の証明]
,
.
[補題2]
のとき,任意の
について
.逆に
のとき,
より
は
上で周期
をもたない.
[補題2の証明]
.
[補題3]
かつ
が
上で周期
をもつとき,
が
上で周期
をもつための必要十分条件は
.
[補題3の証明]
の
への射影を最上位ビット成分
と下位
ビット成分
に分解し,
(
,
)
とする.補題2より
(以下
を省略)
.
について両辺の総和をとると,
より
.
が
上で周期
をもつことから,右辺の
および
は
の値を一度ずつとり,
.
ここで, の
上の周期は
と
のいずれかであるが,
より周期が
となるための必要十分条件は
であり,これにより補題が証明される.
【定理の証明】
補題1および補題2より, かつ
が定理の必要条件となる.この条件のもとで,ある
について
が
上で周期
をもつと仮定する.(
では成立)
このとき補題3より, が
上で周期
をもつための必要十分条件は
.
したがって,これらの条件をまとめて かつ
とすると,補題3および数学的帰納法により任意の自然数
について
が
上で周期
をもつ.■