フェルマーの小定理

フェルマーの小定理は，素数を$p$とし，$p$とは互いに素な整数を$a$として，$a^{p-1} \equiv 1 \quad (\mod p \ ) $というものである。

頭の体操のためによく見ている鈴木貫太郎の YouTubeチャンネルでは，ちょっと目には解きにくそうな整数問題に，縦横無尽にmodを使って条件を絞り込んでいくというパターンがよく見られる。自分が，高校生のときには，こんなふうにしてmodを活用するということがなかったので，新鮮な感じがしている。ここまで自由に使えれば便利には違いない。

そんなわけで，フェルマーの小定理あるいは，その他のmod問題の勘を養成するための１行コードをMathematicaで書いてみた。

f[n_] := Table[ Table[Mod[i^k, Prime[n]], {i, 1, Prime[n]}], {k, 1, Prime[n] - 1}]
g[n_] := Table[Table[Mod[i^k, n], {i, 1, n}], {k, 1, n - 1}]

Do[{Print[g[i], " "]}, {i, 2, 7}]
{{1,0}}
{{1,2,0},{1,1,0}}
{{1,2,3,0},{1,0,1,0},{1,0,3,0}}
{{1,2,3,4,0},{1,4,4,1,0},{1,3,2,4,0},{1,1,1,1,0}}
{{1,2,3,4,5,0},{1,4,3,4,1,0},{1,2,3,4,5,0},{1,4,3,4,1,0},{1,2,3,4,5,0}}
{{1,2,3,4,5,6,0},{1,4,2,2,4,1,0},{1,1,6,1,6,6,0},{1,2,4,4,2,1,0},{1,4,5,2,3,6,0},{1,1,1,1,1,1,0}}