§ 12. Polynomkongruenzen

Im folgenden sei n ∈ ℕ. Wir wollen das folgende Problem behandeln, das in der Algebra dem Lösen von polynomialen Gleichungen entspricht.

\underline{Problem:} Gegeben sei ein Polynom f mit ganzzahligen Koeffizienten, d.h. f ∈ ℤ[T] . Gesucht sind ganze Zahlen x ∈ ℤ mit

(⋆) f(x) ≡ 0 (mod n)

Man nennt (⋆) eine Polynomkongruenz . Jede ganze Zahl x_{1} ∈ ℤ mit f(x_{1}) ≡ 0 (mod n) heißt eine Lösung von (⋆) . Ziel ist es, Aussagen über die Existenz und Anzahl von Lösungen zu erhalten.

\underline{(12.1) LEMMA:} Seien f ∈ ℤ[T] und a, b ∈ ℤ. Dann gilt:

a ≡ b (mod n) ⟹ f(a) ≡ f(b) (mod n)

Ist also x_{1} ∈ ℤ eine Lösung von (⋆) , so ist auch jedes Element aus der Restklasse von x_{1} modulo n eine Lösung von (⋆) , d.h. es gibt unendlich viele Lösungen. Daher wollen wir unter der Anzahl der Lösungen modulo n von (⋆) die Anzahl der modulo n paarweise inkongruenten Lösungen von (⋆) verstehen.

\underline{Lineare Kongruenzen} Wir behandeln zunächst den Fall grad(f) = 1 .

\underline{(12.2) LEMMA:} Sind a ∈ ℤ und n teilerfremd , so besitzt die lineare Kongruenz

(⋆⋆) ax ≡ b (mod n)

genau eine Lösung modulo n.

\underline{(12.3) LEMMA:} Sei g := ggT(a, n) . Genau dann ist die lineare Kongruenz

(⋆⋆) ax ≡ b (mod n)

lösbar, wenn g | b gilt.

\underline{(12.4) SATZ:} Sei g := ggT(a, n) und gelte g | b . Dann besitzt die lineare Kongruenz

(⋆⋆) ax ≡ b (mod n)

genau g Lösungen modulo n. Diese sind gegeben durch

t + k · \frac{n}{g} (k = 0, 1, 2, …, g − 1) ,

wobei t die modulo \frac{n}{g} eindeutig bestimmte Lösung der linearen Kongruenz

(⋆ ⋆ ⋆) \frac{a}{g} · x ≡ \frac{b}{g} (mod \frac{n}{g}) ist.

(12.5) SATZ:

Chinesischer Restsatz

n_{1}, …, n_{r} (r ≥ 2) seien paarweise teilerfremde natürliche Zahlen und b_{1}, …, b_{r} seien beliebige ganze Zahlen. Dann besitzt das folgende System lineraer Kongruenzen genau eine Lösung modulo n := n_{1} · n_{2} · . . . · n_{r}:

(⋆) { x ≡ b_{1} (mod n_{1}) x ≡ b_{2} (mod n_{2}) ⋮ x ≡ b_{r} (mod n_{r})

Polynomkongruenzen höheren Grades

Aus einem Polynom f = ∑_{i=0}^{m} a_{i}T^{i} ∈ ℤ[T] mit ganzzahligen Koeffizienten wird durch Übergang

zu den Restklassen modulo n ein Polynom \overline{f} = ∑_{i=0}^{m}[a_{i}]_{n}T^{i} ∈ ℤ_{n}[T]

\underline{(12.6) LEMMA:} Sei f ∈ ℤ[T] . Dann sind für x_{1} ∈ ℤ folgende Aussagen äquivalent:

a) x_{1} ist eine Lösung der Polynomkongruenz f(x) ≡ 0 (mod n)

b) [x_{1}]_{n} ist eine Nullstelle des Polynoms \overline{f} ∈ ℤ_{n}[T] .

(12.7) SATZ:

von Lagrange

Sei p eine Primzahl und f ∈ ℤ[T] ein Polynom, dessen Leitkoeffizient \underline{nicht} von p geteilt wird. Dann hat die Polyomkongruenz

(⋆) f(x) ≡ 0 (mod p)

höchstens grad(f) Lösungen modulo p.

\underline{(12.8) LEMMA:} Sei f = ∑_{i=0}^{m} a_{i}T^{i} ∈ ℤ[T] ein Polynom vom Grade m, und p sei eine Primzahl. Besitzt dann die Polyomkongruenz

(⋆) f(x) ≡ 0 (mod p)

mehr als m Lösungen modulo p, so gilt

p | a_{i} (∀ i = 0, 1, …, m) .

\underline{(12.9) KOROLLAR:} Sei p eine Primzahl. Dann sind alle Koeffizienten des Polynoms

f := (T − 1) · (T − 2) · . . . · (T − p + 1) − T^{p−1} + 1 ∈ ℤ[T]

durch p teilbar.

(12.10) KOROLLAR: Satz von Wilson

Für jede Primzahl p gilt (p − 1)! ≡ −1 (mod p) .

\underline{(12.11) SATZ:} n_{1}, …, n_{r} (r ≥ 2) seien paarweise teilerfremde natürliche Zahlen und es sei n := n_{1} · n_{2} · . . . · n_{r}. Ferner sei f ∈ ℤ[T] . Dann gilt:

a) Die Polynomkongruenz

(⋆) f(x) ≡ 0 (mod n)

besitzt genau dann eine Lösung, wenn die Polynomkongruenzen

(⋆⋆) f(x) ≡ 0 (mod n_{i})

für jedes i = 1, 2, …, r eine Lösung besitzen.

b) Ist α(n) die Anzahl der Lösungen von (⋆) modulo n und α(n_{i}) die Anzahl der Lösungen von (⋆⋆) modulo n_{i}, so folgt

α(n) = α(n_{1}) · α(n_{2}) · . . . · α(n_{r}) .

\underline{(12.12) KOROLLAR:} Die natürliche Zahl n ≥ 2 besitze die kanonische Primfaktorzerlegung

n = p_{1}^{k_{1}} · p_{2}^{k_{2}} · . . . · p_{r}^{k_{r}} . Dann gilt:

a) Die Polynomkongruenz

(⋆) f(x) ≡ 0 (mod n)

besitzt genau dann eine Lösung, wenn die Polynomkongruenzen

(⋆⋆) f(x) ≡ 0 (mod p_{i}^{k_{i}})

für jedes i = 1, 2, …, r eine Lösung besitzen.

b) Ist a_{i} ∈ ℤ eine Lösung von (⋆⋆) , so ist jede Zahl a ∈ ℤ mit a ≡ a_{i} (mod p_{i}^{k_{i}}) für alle i = 1, 2, …, r eine Lösung von (⋆) .

Chr.Nelius : Zahlentheorie (SS 2007) 4 Wir wollen die spezielle Polynomkongruenz x^{m} − a ≡ 0 (mod n) untersuchen. \underline{(12.13) DEF:} Seien m, n ∈ ℕ und a ∈ ℤ mit ggT(a, n) = 1 . Die Zahl a heißt m–ter Potenzrest modulo n, wenn die Kongruenz

(⋆) x^{m} ≡ a (mod n)

lösbar ist. Probleme: a) Wann existieren m–te Potenzreste modulo n?

b) Wie groß ist die Anzahl der m–ten Potenzreste modulo n?

c) Wie lassen sich m–te Potenzreste modulo n berechnen ? \underline{(12.14) SATZ:} Seien m, n ∈ ℕ. w ∈ ℤ sei eine Primitivwurzel modulo n, und es sei a ∈ ℤ mit ggT(a, n) = 1 . Ferner sei g := ggT(m, φ(n)) . Dann sind folgende Aussagen äquivalent:

a) a ist ein m–ter Potenzrest modulo n

b) g | ind_{w}(a)

c) a ^{\frac{φ(n)}{g}} ≡ 1 (mod n) . Ist eine dieser drei Bedingungen erfüllt (und damit alle) , so hat die Kongruenz (⋆) genau g Lösungen modulo n. \underline{(12.15) BEM:} Sei p > 2 eine ungerade Primzahl. Da es nach (11.14) Primitivwurzeln modulo p^{k} (k ∈ ℕ) gibt, gilt (12.14) insbesondere für den Fall n = p^{k}. \underline{(12.16) SATZ:} a ∈ ℤ sei \underline{ungerade} . Ferner seien k ∈ ℕ , k ≥ 3 und g := ggT(m, 2^{k−2}) . Dann gilt für die Lösbarkeit der Kongruenz

(⋆⋆) x^{m} ≡ a (mod 2^{k})

folgendes:

a) Ist m \underline{ungerade} , so ist (⋆⋆) eindeutig lösbar.

b) Ist m \underline{gerade} , so ist (⋆⋆) genau dann lösbar, wenn gilt i) a ≡ 1 (mod 4)

ii) a ^{\frac{2^{k−2}}{g}} ≡ 1 (mod 2^{k}) .

Ist (⋆⋆) lösbar, so ist die Anzahl der Lösungen von (⋆⋆) modulo 2^{k} gleich 2 · g. \underline{(12.17) BEM:} Unter den Voraussetzungen des Satzes (12.16) gilt also:

a) Ist m \underline{ungerade} , so ist jede ungerade ganze Zahl m–ter Potenzrest modulo 2^{k} (k ≥ 3) .

b) Ist m \underline{gerade} , so ist eine ungerade ganze Zahl a genau dann ein m–ter Potenzrest modulo 2^{k}, wenn die beiden Bedingungen i) und ii) erfüllt sind. Die Anzahl der Lösungen von (⋆⋆) modulo 2^{k} ist dann gleich

2 · ggT(m, 2^{k−2}) .