リフルシャッフルの数理

さらに，こんな投げかけはどうだろうか?
p=13 として， l 回シャッフルした後のカードの順列を言い当ててあげよう。

定理 3-5の系
mod p の 2 の逆元を a とする。 すなわち 2a ≡ 1 (mod p)
初期状態から l 回のシャッフル後 k の位置にあるカードは \(a^l\cdot k\) (mod p) である。

13を法とするとき2の逆元を求めてみる。
2a - 13b = 1 の整数解を求めるのだが， 2の倍数を順にあげて，2× 7 = 14 したがって，2の逆元は7である。
(実は，p を奇数とすると，2 の逆元は \(\dfrac{p+1}{2}\) である。 計算上の明らかにそうであるし， シャッフルの仕組みをみても確かにそうである!!)
初期状態の1回のシャッフル後は，確かに7の倍数の13で割った余りが並ぶ。
\( \begin{array}{ccccccccccccc} 0 & 7 & 14 & 21 & 28 & 35 & 42 & 49 & 56 & 63 & 70 & 77 & 84\\ 0 & 7 & 1 & 8 & 2 & 9 & 3 & 10 & 4 & 11 & 5 & 12 & 6\\ \end{array} \)
(上の行7の倍数，下の行13で割った余り)
5 回シャッフルした後は \(7^5\equiv 11\) (mod 13) だから 11 の倍数の 13 で割った余りが並ぶ。
\( \begin{array}{ccccccccccccc} 0 & 11 & 22 & 33 & 44 & 55 & 66 & 77 & 88 & 99 & 110 & 121 & 132\\ 0 & 11 & 9 & 7 & 5 & 3 & 1 & 12 & 10 & 8 & 6 & 4 & 2\\ \end{array} \)
(上の行11の倍数，下の行13で割った余り)

つまり 7のl乗 (実際は 7 倍しては 13 で割った余りをとることを繰り返す) と
その (k とする) 倍数 (実際は k を足しては 13 で割った余りをとることを繰り返す)で，
カードの順列を言い当てることができる。