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/2aZ) für a > 2.
Behauptung: E ist als inneres direktes Produkt mit den zyklischen Faktoren
< ¯5 > und < ¯3 > darstellbar. (|E| = |2a - 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 2aZ.
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 + 1Z.
Nach der 1.) Vermutung gilt: (5) (2) ^ (a - 1) ist aus 2 xZ und (5) (2) ^ ((a - 1) - 2)- 1 ist aus 2 a - 1Z.
Zu zeigen: y ist nicht aus 2 a + 1Z, das heißt 2 a + 1 teilt nicht y.
Betrachte: y = x2 + 2x; 2 a teilt nicht x; 2 a + 1 teilt nicht 2x.
Zu Zeigen: 2 a + 1 teilt x2
Wir wissen: 2 a - 1 teilt nicht x, also: (2 a - 1 ) ^ 2 =2 (a - 1) 2 teilt x2 . Es gilt: 2a - 2 = a + (a - 2) und a - 2 > 0, da a > 2.
Es folgt: 2 a + 1 teilt x2 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/2aZ) .
Beweis: Es gilt: 5 ist kongruent 1 modulo 4. Daraus folgt: 5r ist kongruent 1 modulo 4 für jede natürliche Zahl r. Daraus folgt 1 ist nicht kongruent (- 1) modulo 4
und 5r ist nicht kongruent (- 1) modulo 4. Daraus folgt: 5r ist nicht kongruent zu - 1 modulo 2a.
Es folgt also: (- ¯1) ist nicht aus < ¯5 > in E (Z/2aZ)
Also ist E vom Isomorphietyp: C 2 ^ (a - 2) * C 2 (* 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 pa .
2) g ist Primitivwurzel modulo p und g (p - 1) ist nicht kongruent zu 1 modulo p2.
3) g ist Primitivwurzel modulo p2.
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 pa , für alle a größer gleich zwei, falls g (p - 1) nicht kongruent ist zu 1 modulo p2 .
b) so ist g + p eine Primitivwurzel modulo pa , für alle a größer gleich zwei, falls g (p - 1) kongruent ist zu 1 modulo p2 .
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:
00-09 |
USA, Kanada |
73 |
Schweden |
30-37 |
Frankreich |
76 |
Schweiz |
40-43 |
Deutschland |
80-81 |
Italien |
49 |
Japan |
84 |
Spanien |
50 |
Großbritannien |
87 |
Niederlande |
54 |
Belgien |
90-91 |
Österreich |
57 |
Dänemark |
93 |
Australien |
64 |
Finnland |
60 |
Südafrika |
70 |
Norwegen |
978 |
Bücher |
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?
Fehler |
Fehlerentdeckrate |
Ziffer vergessen |
100,00% |
Ziffer zuviel eingetippt |
100,00% |
Ziffer mit Nachbarn vertauscht |
88,88% |
Ziffernblöcke vertauscht |
0,00% |
Ziffer falsch eingetippt |
100,00% |
2 Ziffern falsch eingetippt |
90,00% |
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:
Fehlertyp |
Häufigkeit |
Zu viele oder zu wenige Ziffern |
25% |
Vertauschen benachbarter Ziffern |
5% |
Vertauschen benachbarter Zweierblöcke |
1% |
Eine Ziffer falsch |
60% |
Zwei oder mehr Ziffern falsch |
8% |
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.ä..