■剰余の計算(その26)

なぜ1/7は長さ6の周期をもつのだろうか?

  10^k=1  (mod7)

となる最小のkを探して、k=7−1であることを示すことになるが、pが大きいとき、k=1,2,3,・・・と順に探すのは大変である。

===================================

2、5でない素数pに対して、

  n=Πpi^ni

の10進展開は、各piに関する10の位数の最小公倍数に等しい周期をもつ。

すなわち、ki=ordpi^ni(10)をもちいて、周期T=[k1,k2,・・・]

nが2、5を含む場合、10進小数は非循環頭部をもつことになる。

===================================

1/119=1/7・1/17の場合、T=[6,16]=48

1/2737=1/7・1/17・1/23の場合、T=[6,16,22]=528

===================================

ordp(10)はp-1か、p-1の約数である。

p-1となるのが10がpの原始根であるときで、10は

p=7,17,19,23,29,47,59,61,97などの原始根である。

p=11,13,・・・はordp(10)はp-1か、p-1の約数である。

===================================

10進分数について述べてきたことは他に基底に対しても当てはまる。たとえば、

2進法における1/3は周期T=ord3(2)=2をもつ。

2進法における1/5は周期T=ord5(2)=4をもつ。

素数9949は2を原始根にもつ、ord9949(2)=9948

1/9949は周期長9948=2^2・3・829をもつ0/1数列を生成する。

素数9851は2を原始根にもつ、ord9851(2)=9850

1/9851は周期長9950=2・5^2・197をもつ0/1数列を生成する。

したがって、1/99007599=1/9949・1/9851の2進数展開は周期長9950=[2^2・3・829,2・5^2・197]=48993900

の長い擬似ランダム2進数列を生成する。

===================================