Elementare Zahlentheorie WS 2003/04

Protokoll vom 20.11.03 (AE)

Themen der Stunde:     

1) Die Einheitengruppe E (Z/2 ^aZ) für a > 2

2) Prüfcodes

Zu 1): 

Es sei E := E (Z/2^aZ) für a > 2.

Behauptung: E ist als inneres direktes Produkt mit den zyklischen Faktoren  

< ¯5 > und < ¯3 > darstellbar. (|E| = |2^{a - 1}|)

1. Vermutung: (¯a) ^{(2) ^ (a - 2)} =¯1 für alle ¯a aus E.

2. Vermutung: o(¯5) = 2 ^{a - 2}

Zu zeigen: (¯5) ^{(2) ^ (a - 3)} ist nicht gleich ¯1 in Z/2 ^aZ (a > 2)

Induktionsvorrausetzung:  (¯5) ^{(2) ^ (a - 3)} ist nicht gleich ¯1 in Z/2 ^aZ (a > 2), 

das heißt x :=  (¯5) ^{(2 ) ^  (a - 3)} - 1 ist nicht aus 2^aZ.

Zu zeigen: (~5) ^{(2) ^ (a-2)}  ist nicht gleich ~1 in Z/2 ^{(a + 1)}Z, das heißt y := (¯5) ^{(2) ^ (a - 2)} - 1 ist nicht aus 2 ^{a + 1}Z.

Nach der 1.) Vermutung gilt: (5) ^{(2) ^ (a - 1)} ist aus 2 ^xZ und (5) ^{(2) ^ ((a - 1) - 2)}- 1 ist aus 2 ^{a - 1}Z.

Zu zeigen: y ist nicht aus 2 ^{a + 1}Z, das heißt 2 ^{a + 1} teilt nicht y. 

Betrachte: y = x² + 2x; 2 ^a teilt nicht x; 2 ^{a + 1} teilt nicht 2x. 

Zu Zeigen: 2 ^{a + 1} teilt x² 

Wir wissen: 2 ^{a - 1} teilt nicht x, also: (2 ^{a - 1} ) ^ 2 =2 ^{(a - 1) 2} teilt x² . Es gilt: 2a - 2 = a + (a - 2) und a - 2 > 0, da a > 2.

Es folgt: 2 ^{a + 1} teilt x²  und 2 ^{a + 1} teilt nicht 2x. Damit folgt: 2 ^{a + 1} teilt nicht y.

Es bleibt noch zu zeigen, dass < ¯5 > und < ¯3 > ein inneres direktes Produkt bilden.

3. Vermutung: - ¯1 ist nicht aus  < ¯5 >  in E (Z/2^aZ) .

Beweis: Es gilt: 5 ist kongruent 1 modulo 4. Daraus folgt: 5^r  ist kongruent 1 modulo  4  für jede natürliche Zahl r. Daraus folgt 1 ist nicht kongruent (- 1) modulo 4 

und 5^r  ist nicht kongruent  (- 1) modulo  4. Daraus folgt: 5^r  ist nicht kongruent zu  - 1 modulo  2^a.          

Es folgt also: (- ¯1) ist nicht aus  < ¯5 >  in E (Z/2^aZ) 

Also ist E vom Isomorphietyp: C _{2 ^  (a - 2)} * C ₂ (* steht hier für das kartesische Produkt bzw. äußere Produkt)

Fazit:  

Die Einheitengruppe von Z/2 ^aZ ist inneres direktes Produkt der zyklischen 

Faktoren < ¯5 > und < ¯3 >. Damit haben wir die Struktur der Gruppe analysiert, indem wir die Gruppe in unzerlegbare Bausteine (zyklische Gruppen) zerlegt haben. 

Verallgemeinerung (ohne Beweis):

SATZ A:

Für eine Primzahl p ungleich 2, eine natürliche Zahl a größer gleich 2 und eine ganze Zahl g sind folgende drei Aussagen äquivalent:

1) g ist Primitivwurzel  modulo  p^a .

2) g ist Primitivwurzel modulo p und g ^{(p - 1)} ist nicht kongruent zu 1 modulo p².

3) g ist Primitivwurzel modulo p².

SATZ B:

Ist p eine Primzahl ungleich 2, g eine ganzzahlige Primitivwurzel modulo p (deren Existenz haben wir bereits bewiesen),

a) so ist g eine Primitivwurzel modulo  p^a , für alle a größer gleich zwei, falls g ^{(p - 1)}  nicht kongruent ist zu 1 modulo  p² .

b) so ist g + p eine Primitivwurzel modulo  p^a , für alle a größer gleich zwei, falls g ^{(p - 1)}  kongruent ist zu 1 modulo  p² .

Zu 2):   

§ 3 Prüfcodes

Als erstes Beispiel haben wir die Europäische Artikelnummer (EAN) betrachtet. Die EAN ist 13-stellig.

Beispiele für typische EANs:

40 28700 071010 Immenhof Honig

40 08535 264948 Reisetti Kochbeutel-Reis (Plus)

40 00345 060888 neuform Gemüsebrühe     usw.

Was bedeuten die Ziffern?

Die ersten beiden Ziffern bilden die Länderkennzahl, die folgende vierstellige Nummer ist die Betriebsnummer, die darauf folgende fünfstellige Nummer ist die Artikelnummer und bei der letzten Zahl handelt es sich um die so genannte Prüfziffer. 

EAN- Länderkennzahlen:

Wie funktioniert das Prüfverfahren?

Vorgehen: Man multipliziert die Ziffern der EAN (bis auf die letzte) abwechselnd mit eins und drei, die so neu entstandenen Ziffern  summiert man auf. Die erhaltene Summe muss nun bei der Division durch zehn null ergeben. 

Erkennt die Prüfziffer alle Fehler?

Beträgt die Fehlerentdeckrate eines Fehlers 100%, so deckt das Prüfverfahren den Fehler in jedem Fall auf. 

Welche Fehler tauchen häufig auf? Und wie häufig? Hier das Ergebnis einer statistischen Untersuchung:

Problem dieser Tabelle: Man weiß nicht unter welchen Bedingungen die Fehler passieren, ob beim Eintippen der EAN in die Kasse oder beim Einlesen durch einen Scanner o.ä..