G[k] = | {e ∈ G | o(x) = k} | G ist zyklisch, d.h. G = Z / mZ = H, H ist zyklisch H(k) ≤ k H(k) = k ≤ G(k) ≤ G[k], | H | = m = | G |
für k | m G = Uk | mG'[k]
| G | = Sk | mG[k]
ist gleich der Menge {x ∈ G | o(x) = k}
H = Uk | mH'[k]
| H | = Sk|m H[k].
[Gilt H[k] ≥ G[k] für alle k | m? Denn dann H[k] = g[k] für alle k | m, also insbesondere H[m] = G[m], G zyklisch. || ≠ 0 , etwa o(g) = m = | < g > | = | G |, = G. ]
Noch zu zeigen: H[k] ≥ G[k] für alle k | m.
1.Fall: G[k] = 0. okH[k] > 0
2.Fall: Es existiert y ∈ G mit o(y) = k: mit k ≥ G(k) und (k) = k
also G(k) = k und G[k] = H[k].
Def.:n ∈ Z, m ∈ Z heißt Primitivwurzel mod n, wenn E(Z / nZ) zyklisch ist [mit Q(n) Elementen] und <m> = E(Z / nZ) und
gilt [o(m) = φ(n)].
Liste der kleinsten positiven Primitivwurzeln mod p für die P2p <100:
0 < m,
E(Z / pZ) = Cp-1 φ(p) = p - 1
1
2
2
3, 5, 11, 13, 19, 29, 37, 53, 59, 61, 76, 83
3
7, 17, 31, 43, 79, 89
5
23, 47, 73, 97
6
41
7
71
Schreiben zu 2)
Sei n = 2ä mit a > 3 q(2ä) = 2ä-1 = E(Z / 2äZ).
1. Vermutung
a2a-1 = 1 für alle a ∈ E = E(Z/2aZ). Beweis:
i) a = 3 : E = E(Z / 8Z) = {1,3,5,7} = C2xC2.
Zu zeigen a2 = 1 für a ∈ E q = 4 : E(Z / 16Z) = <5> * <-1>.
Zu zeigen 54 = 1 !
xl = 1 in (Z/2aZ) bedeutet:
xl ≡ 1 mod 2a , xl - 1 ≡ 0 , aa | xl - 1.
ii) Vollständige Induktion nach a
Induktionsschritt:
Es sei a > 3.
Es gelte x2a - 2 ≡ 1 mod 2a für alle x ∈ E (Z/2aZ) d.h. für alle x ∈ Z mit 2 + x.
[Zu zeigen x2a - 1 ≡ 1 mod 2a + 1 für alle 2 † x ∈ Z.]
Es folgt: x2a-2 = 1 + 2a * d für ein d ∈ Z, x2a - 1 = xaa - 2 * 2 = (x2a - 2)2 = (1 + 2ad)2
= 1 + 2a - 1d + (2ad)2 ≡ 1 mod 2a + 1. ||