Lexikon der Mathematik: n-ter Potenzrest
Begriff aus der Zahlentheorie.Sind m, n ∈ ℕ und c ∈ ℤ mit ggT(c, m) = 1, und gibt es eine ganze Zahl x, die die Kongruenz
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 eine Primitivwurzel 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:
- c ist ein nter Potenzrest modulo m.
- Es gilt cφ(m)/d ≡ 1 mod m.
- 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.
Schreiben Sie uns!