Zusammenfassung Vorlesung 6 - Arithmetik Grundschule PDF

Preview

Summary

Satz von Euklid
Primzahlzwillinge
Mirpzahlen
Mersenne-Primzahlen
Fermatsche Primzahlen
Zerlegungsbäume
Primfaktorzerlegung...

Description

Vorlesung 6 Anzahl der Primzahlen Satz 3: Satz von Euklid Es gibt unendlich viele Primzahlen.

Primzahlzwillinge Primzahlzwillinge nennt man diejenigen Primzahlen, deren Differenz 2 ist. Beispiel: (3, 5) à 5 - 3 = 2 Alle Primzahlzwillinge zwischen 1 und 100 à Sieb des Eratosthenes durchführen und Primzahlzwillinge ablesen: (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73)

Mirpzahlen Mirpzahlen sind Primzahlen, die rückwärts gelesen eine andere Primzahl ergeben Beispiel: 13 ist eine Mirpzahl, da 31 eine Primzahl ist bzw. ist 31 eine Mirpzahl, weil 13 eine Primzahl ist. Alle Mirpzahlen zwischen 1 und 100 à Sieb des Eratosthenes durchführen und Mirpzahlen ablesen: (13, 31), (17, 71), (37, 73), (79, 97)

Mersenne-Primzahlen (besondere Primzahlen) Die Zahl 2! - 1 ist eine Mersenne-Primzahl. Beispiel: 2" - 1 = 1 2# - 1 = 3 2$ - 1 = 7 2% - 1 = 15 2& - 1 = 31

Fermatsche-Primzahlen (besondere Primzahlen) Die Zahl 2! + 1 ist eine Fermatsche-Primzahl. Beispiel: 2" + 1 = 3 2# + 1 = 5 2$ + 1 = 9 2% + 1 = 17 2& + 1 = 33

Primzahlen als Bausteine der natürlichen Zahlen 90 als Produkt von 2 Zahlen: 90 = 2 • 45 = 3 • 30 = 5 • 18 = 9 • 10 90 als Produkt von 3 Zahlen: 90 = 2 • 3 • 15 = 2 • 5 • 9 = 3 • 5 • 6 = 3 • 3 • 10 90 als Produkt von 4 Zahlen: 90 = 2 • 3 • 3 • 5 à 90 als Produkt von 5 Zahlen gibt es nicht, weil bei 90 als Produkt von 4 Zahlen nur noch Primzahlen „über“ sind

Zerlegungsbäume

à Primfaktorzerlegung 60 = 𝟐𝟐 ∙ 𝟑% ∙ %𝟓

Satz 1: Existenz der Primfaktorzerlegung Jede von 1 verschiedene natürliche Zahl besitzt mindestens eine Primfaktorzerlegung

Beispiel: 420 = 2 • 210 = 2 • 2 • 105 = 2 • 2 • 3 • 35 = 2 • 2 • 3 • 5 • 7 à 2# • 3 • 5 • 7

p=abgespaltene Primzahl n= abgespaltene natürliche Zahl 𝑝" = 2; 𝑝# = 2; 𝑝$ = 3; 𝑝% = 5 𝑛" = 210; 𝑛# = 105; 𝑛 = 35; 𝑝% = 7

à dieser Prozess wird so lange fortgeführt, bis der kleinste Teiler (aber von 1 verschieden) von einer vorgegebenen natürlichen Zahl abgespalten ist.

Beweis: Fall 1: die vorgegebene natürliche Zahl a ist eine Primzahl à Primzahl a = a (Primfaktorzerlegung fertig; man kann nicht weiter aufspalten) Beispiel: 73 = 73 Fall 2: die vorgegebene Zahl a ist keine Primzahl, so wird der kleinste von 1 verschiedene Teiler 𝑝" von a abgespalten und wir erhalten a = 𝑝"( • % 𝑛" % Ist 𝑛" eine Primzahl, so liegt eine Primfaktorzerlegung von a vor und wir sind fertig. Fall 3: ist 𝑛" keine Primzahl, dann können wir den kleinsten von 1 verschiedenen Teiler 𝑝#(von%𝑛"( abspalten und erhalten: 𝑛"()( 𝑝# ⋅ 𝑛# Ist 𝑛# nun eine Primzahl, so sind wir fertig, da wir eine Primfaktorzerlegung von a erhalten haben. Fall 4: ist 𝑛# immer noch keine Primzahl, dann können wir den kleinsten von 1 verschiedenen Teiler 𝑝$(von%𝑛#(abspalten und erhalten: 𝑛#()( 𝑝$ ⋅ 𝑛$ Ist 𝑛$ nun eine Primzahl, so sind wir fertig, da wir eine Primfaktorzerlegung von a erhalten haben. Fall 5: ist 𝑛$ %jedoch keine Primzahl wird dieser Prozess so lange fortgeführt bis wir eine Primfaktorzerlegung haben. q.e.d.

Satz 2: Hauptsatz der elementaren Zahlentheorie Jede von 1 verschiedene natürliche Zahl besitzt (bis auf die Reihenfolge der Faktoren) genau eine Primzahl. (hierfür ist kein Beweis notwendig für die Klausur) à aber wäre 1 eine Primzahl wäre der Hauptsatz der elementaren Zahlentheorie (= der Hauptsatz der Arithmetik) falsch. Dann würde sogar jede natürliche Zahl mehrere Zerlegungen haben.

Satz 3: Primzahlkriterium Die von 1 verschiedene natürliche Zahl d ist ganz dann eine Primzahl, wenn für alle natürlichen Zahlen a, b gilt: aus d | a • b folgt à d | a oder d | b à gilt nur für Primzahlen, also eine charakteristische Eigenschaft der Primzahlen!

Beispiel: d=3 a=4 b=6 3 teilt 4 • 3 à 3 | 24 3 teilt nicht a also 4 ABER 3 teil b also 6 à 3 | 6 • •

d ist eine Primzahl und es gilt d | a • b dann gilt stets d | a oder d | b

somit existiert stets eine natürliche Zahl n mit n • d = a • b die Primzahl d muss auch in der Primfaktorzerlegung von a • b vorkommen, also in der Primfaktorzerlegung von a oder b oder von a und b.

Kontraposition (2. Beweisrichtung) Ist die von 1 verschiedene Zahl d keine Primzahl, dann gilt nicht für alle natürlichen Zahlen a, b: aus d | a • b folgt à d | a oder d | b wäre d also keine Primzahl, sondern eine zusammengesetzte Zahl d = a • b mit natürlichen Zahlen zwischen 1 und d, gilt: d | a • b da d |d aber auch d ∤ a und d ∤ b q.e.d.

Satz 4: Lemma von Euklid Lemma (= Hilfssatz) Ist p eine Primzahl und gilt p | a • b, so folgt p |a oder p | b

Satz 5: Die Teilermenge T (a) mit a = 𝑝* besitzt genau (m + 1) Teiler, die Teilermenge von T (a) mit 𝑝* • %𝑞! besitzt genau (m + 1) • (n + 1) Teiler, wenn p und q verschiedene Primzahlen sind

à Rückgriff auf das Rechteckschema

Merke: 𝒏𝟎 ist immer 1, egal welche Zahl wir für n einsetzen „irgendwas hoch null ist immer 1“

Bsp.: T (72) Primfaktorzerlegung: 72 = 𝟐𝟑 ∙ 𝟑𝟐 T (72) = {2$ ∙ 3# + 𝑛} = {m + 1}

n=1

Rückgriff auf das Rechteckschema: •

3-

3"

3#

2-

1

3

9

2"

2

6

18

2#

4

12

36

2$

8

24

72

à T (72) = {1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72}...