Zahlentheorie-Fortsetzung

Aufgaben zum Üben

  1. Rechnen modulo: Berechne (23 + 48) 10.
  2. Potenz modulo: Berechne 7^100 5.
  3. Kongruenz: 17 2 5.
  4. Produkt modulo: Berechne (14 · 9) 5.
  5. Chinesischer Restsatz: Kleinste positive Zahl mit Rest 2 bei Division durch 3 und Rest 3 bei Division durch 5?
  6. Euler'sche Phi-Funktion: Berechne (84) ( ist die Euler’sche Phi-Funktion).
  7. Wochentag: Heute ist Montag. Welcher Wochentag ist in 100 Tagen? (Montag = 0, Dienstag = 1, …, Sonntag = 6)
  8. Prüfziffer: Bei einer Prüfziffer gilt: Summe der Ziffern 0 10. Welche Prüfziffer gehört zu 4\,7\,3\,8?
  9. Restklasse bestimmen: In welche Restklasse gehört die Zahl a) 67 bezüglich des Moduls 8 b) 2749 bezüglich des Moduls 12 c) 50876 bezüglich des Moduls 121 Gib für c) den Rest an.
  10. Inverse: Welche Zahl x \1, , 6\ erfüllt 3x 1 7?
  11. Fermat: Berechne 2^12 13.
  12. Anzahl der Gruppenaxiome: Zeige, dass die Menge der primen Restklassen modulo 3: R_3^* = \ 1+3Z, 2+3Z \ zusammen mit der (Restklassen-)Multiplikation eine Gruppe bildet. Gib die Anzahl der Regeln ein, die du überprüfen musst, um zu zeigen, dass …

Wichtige Begriffe

Gruppe
Mit ganzen Zahlen und Plus, mit Uhrzeiten, mit [[Restklassen-Addition|Restklassen]] oder mit Drehungen eines Quadrats – überall gelten dieselben vier Spielregeln: Man bleibt in der Menge, Klammern …
Restklassen modulo m
Im Sportunterricht wird abgezählt: „1, 2, 3, 1, 2, 3, …“ – und alle mit derselben Nummer bilden ein Team. Wer an Platz 1, 4, 7, 10, steht, landet im selben Team. Genauso sortiert man alle ganzen …
Division mit Rest
Wenn wir eine Zahl durch eine andere teilen, geht das nicht immer perfekt auf. Stell dir vor, du möchtest 7 Bonbons gerecht an 3 Freunde verteilen. Jeder bekommt 2 Bonbons, aber ein Bonbon bleibt …
Prime Restklassen
Bei normalen Zahlen kann man jede Zahl außer 0 „rückgängig malnehmen“: 3 · 1/3 = 1. Bei [[Restklassen modulo m|Restklassen]] gibt es keine Brüche. Trotzdem findet man oft ein Gegenstück: In Z_10 ist …
Satz von Euler-Fermat
Welche Ziffer steht am Ende von 7^20? Die Zahl hat 17 Stellen – ausrechnen will das keiner. Schauen wir auf die letzten Ziffern der Potenzen: | k | 1 | 2 | 3 | 4 | 5 | 6 | …
Erweiterter euklidischer Algorithmus
Mit dem [[Euklidischer Algorithmus|euklidischen Algorithmus]] finden wir den ggT. Manchmal wollen wir aber mehr wissen: Wie setzt sich der ggT aus den beiden Zahlen zusammen? Beispiel: Du hast nur …
Euklidischer Algorithmus
Wie findet man den [[Größter gemeinsamer Teiler|ggT]] von 1071 und 462? Alle Teiler auflisten dauert ewig, die [[Primfaktorzerlegung]] ist bei großen Zahlen mühsam. Der Grieche Euklid hat schon vor …
Euler'sche Phi-Funktion
Wie viele Zahlen von 1 bis 12 haben mit der 12 keinen gemeinsamen Teiler (außer 1)? Durchzählen: 1, 5, 7, 11 – also 4 Stück. Diese Anzahl braucht man in der Zahlentheorie ständig: Sie sagt, wie viele …
Kongruenz modulo
3 Uhr nachmittags und 15 Uhr sind auf der Zeigeruhr dieselbe Stelle. Ebenso 2 Uhr und 14 Uhr. Für die Uhr sind solche Zahlen „gleich gut“ – sie lassen beim Teilen durch 12 denselben [[Rest]]. Diese …
Menge der primen Restklassen
In Z_8 gibt es acht Klassen 0, , 7. Wer malnehmen und wieder rückgängig machen will, kann aber nur mit den Klassen arbeiten, die ein Inverses haben – das sind die [[Prime Restklassen|primen …
Menge der Restklassen modulo m
Eine Zeigeruhr kennt nur 12 Stellen. Egal ob 3, 15, 27 oder -9 Stunden – der Zeiger landet immer auf einer dieser 12 Stellen. Die Uhr braucht also nicht unendlich viele Zahlen, sondern nur 12 …
Modul-Begriff
Es ist 10 Uhr. Wie spät ist es in 5 Stunden? Nicht „15 Uhr“ auf einer Zeigeruhr – der Zeiger steht auf der 3. Die Uhr fängt nach 12 einfach wieder von vorne an. Sie interessiert sich nur für den Rest …
Primfaktorzerlegung
So wie man ein Lego-Modell in einzelne Steine zerlegen kann, kann man jede Zahl in Primzahlen zerlegen – die kleinsten Bausteine, die sich nicht weiter teilen lassen. 60 = 2 · 30 = 2 · 2 · 15 = 2 · 2 …
Restklassen-Addition
Es ist 9 Uhr. In 7 Stunden ist es … 16 Uhr – auf der Zeigeruhr also 4 Uhr. Die Uhr rechnet 9 + 7 = 4. Klingt falsch, ist aber genau richtig, wenn man nur auf den Rest modulo 12 schaut. Das ist die …
Restklassen-Multiplikation
Ein Film dauert 5 Stunden – und du schaust ihn 5-mal hintereinander. Wo steht der Stundenzeiger danach, wenn du um 0 Uhr anfängst? 5 · 5 = 25 Stunden, auf der Uhr also 1 Uhr. Modulo 12 gilt: 5 · 5 = …