[分享] 素数的本原根

elim

设正整数 n > 1, 若正整数 g 使 g (mod n), g^2 (mod n),..., g^{n-1} (mod n)
构成 1, 2, ..., n-1 中与 n 互素的元的一个置换, 则称 g 为 n 的本原根.

例1  n = 5, g = 2. 易见 2≡2，2^2 ≡ 4, 2^3 ≡ 3, 2^4 ≡ 1 (mod 5),
2,4,3,1 是 1,2,3,4 的一个重排, 所以 2 是 5 的本原根.

例2  易见 n 的本原根必与 n 互素.  n = 6 以内与 n 互素的的只有 1, 5
但显然 {1^k (mod 6)}, {5^k(mod 6)} 都不构成 1,2,3,4,5 的置换,
所以 n = 6 没有本原根.

以下给出数论的一个经典结果：每个素数都有本原根. 若对论证有疑问，
对涉及概念不清楚，或有更初等的证明，请回帖分享。

simpley

g是原根，则g∧m必不与1同余(m小于p－1).(p－g)∧m－g∧m能被p整除，所以(p－g)∧m不与1同余，那么其必为原根。