本原根

素數p的原根定義

如果a是素數p的原根，則數 , , … , 是不同的並且包含1到的整數的某種排列。

特別地，如果a是素數p的本原根，則在 下都不相同。

若A為模n的本原根，則A，A的平方，A的3次方，……，A的φ(n)次方模n的餘數互不相同，而且構成一個模n的簡化剩餘系。

應用本原根可以證明：若 ，則x為模n的二次剩餘；若 ，則x為模n的非二次剩餘。