Begriff aus der Zahlentheorie.Sind m, n ∈ ℕ und c ∈ ℤ mit ggT(c, m) = 1, und gibt es eine ganze Zahl x, die die Kongruenz \begin{eqnarray}\begin{array}{cc}\begin{array}{cc}{x}^{n}\equiv c & \mathrm{mod}\,m\end{array} & (1)\end{array}\end{eqnarray}

erfüllt, so nennt man c einen n-ten Potenzrest modulo m.

Der folgende Satz ist grundlegend für die Entscheidung, ob ein gegebenes c ∈ ℤ mit ggT(c, m)= 1 ein n-ter Potenzrest modulo m ist.

Seien m, n ∈ ℕ und c ∈ ℤ mit ggT(c, m) = 1 derart, daß es einePrimitivwurzel modulo m gibt, und bezeichne d := ggT(n, φ(m)) (φ(m) ist die Anzahl der zu m teilerfremden Restklassen modulo m,Eulersche φ-Funktion). Dann sind äquivalent:

1. c ist ein nter Potenzrest modulo m.
2. Es gilt c^φ(m)/d ≡ 1 mod m.
3. Für jede Primitivwurzel a modulo m teilt d den Index der Zahl c bezgl. a, also die kleinste ganze Zahl j ≥ 0 mit der Eigenschaft\begin{eqnarray}{a}^{j}\equiv c\,\mathrm{mod}\,m.\end{eqnarray}

Besonderes Interesse verdienen die n-ten Potenzreste für n = 2, die sogenannten quadratischen Reste.