Chr.Nelius : Zahlentheorie (SS 2007) 1

\underline{(16.4) SATZ:} \underline{(Rabin , 1980)}

Sei n > 1 eine ungerade natürliche Zahl, und es gelte

n − 1 = 2^{e} · u (e ≥ 1 , ggT(u, 2) = 1) .

Dann sind folgende Aussagen äquivalent:

a) n ist eine Primzahl

b) Für alle a ∈ ℤ mit ggT(a, n) = 1 und a^{u} ≢ 1 (mod n) gibt es ein k ∈ {0, 1, 2, …, e−1} mit

a2^{k}u ≡ −1 (mod n) .

Für den Beweis von (16.4) (Beweisrichtung “b) ⟹ a)”) benötigen wir den folgenden Hilfssatz.

Für m ∈ ℕ sei ν_{2}(m) := max{ k | k ∈ ℕ_{0} , 2^{k} | m }.

\underline{(16.5) HILFSSATZ:} Sei n > 1 eine ungerade natürliche Zahl mit der Primfaktorzerlegung n = p_{1}^{k_{1}} · p_{2}^{k_{2}} · . . . · p_{r}^{k_{r}} wobei p_{1}, p_{2}, …, p_{r} paarweise verschiedene Primzahlen sind. Ferner sei

n − 1 = 2^{e} · u (e ≥ 1 , ggT(u, 2) = 1) .

Dann gilt für

ν := min{ ν_{2}(p_{i} − 1) | i = 1, 2, …, r}

a) ν ≤ e

b) Genau dann ist ν = e, wenn die Zahl

| { i | 1 ≤ i ≤ r , k_{i} ungerade , ν_{2}(p_{i} − 1) = ν } |

ungerade ist.