Woche 4 Primzahlen und Teilbarkeit PDF

Preview

Summary

Woche 4 Primzahlen und Teilbarkeit...

Description

17.11.2020

Mathematik 1 für Informatik - Primzahlen und Teilbarkeit Primzahlen Teilbarkeit 1: Definition Primzahl: Eine natürliche Zahl p > 1 heißt Primzahl, wenn sie nur durch sich selbst und 1 teilbar ist. Die Menge aller Primzahlen wird mit � bezeichnet.

Satz: Primfaktorzerlegung Jede natürliche Zahl größer als 1 lässt sich eindeutig (bis auf die Reihenfolge) als Produkt von Primzahlen schreiben.

Satz: Euklid Es gibt unendlich viele Primzahlen

Bemerkung: Der Primzahlsatz sagt, dass

π (n):=|{ p ∈ � : p ≤ n }|≈

n ln(n)

lim π (n) ln ( n) n→∞

n

=1

Notation: Für Zahlen a , b ∈ ℤ schreibt man ein m ∈ ℤ gibt mit b=m∗a

a∨b (man spricht a teil b), falls a ein Teiler von b ist, d.h. falls es

Definition: ggT Für a , b ∈ ℤ , a ≠ 0 , heißt die größte natürliche Zahl n ∈ℕ mit n|a und n|b der größte gemeinsame Teiler von a und b. Er wird mit ggT(a,b) bezeichnet.

17.11.2020

Lemma: Rechenregeln für ggT Seien a , b ∈ ℤ und m∈ ℤ i) ggT (a , b)= ggT (b , a)= ggT (− a , b )= ggT (a ,−b )=ggT (− a ,−b ) z.B. ggT (9,6)= ggT (− 9,6 )=3 ii)

ggT (a , b)=ggT (a+m∗b ,b)=ggT (a ,b+ m∗a)

Lemma: Division mit Rest a , b ∈ ℤ . Dann gibt es eindeutige a=q∗b∗r .

Sei

q ∈ ℤ und r ∈{0,...... , b−1} mit

r heißt Rest von a bei Divisionen durch b und wird mit a mod b bezeichnet (gesprochen: ,,a modulo b” oder einfach ,,a mod b”)

Bemerkung: Fpr

a , b ∈ ℤ ist

ggT (a .b )=ggT ( a mod b , b )

(gilt mit ii) aus Lemma: Rechenregeln ggT )

17.11.2020

Euklidischer Algorithmus: Satz: Euklidischer Algorithmus Seien a , b ∈ℕ und sei a ≥ b . Das folgende Verfahren, der sogenannte Euklidische Algorithmus, berechnet (rekursiv) ggT(a,b). 1. Berechne r = a mod b 2. Ist r = 0, dann ggT(a,b) = b und Stop! 3. Rufe das Verfahren auf für a = b und B=r, d.h. berechne ggT(b, a mod b)

Beispiel: Berechnen von ggT(29393,2805): Aufruf von ggT(a,b)

r= a mod b

Notizen

ggT(29393,2805)

1343

=29393 mod 2805 (Schritt 1)

ggT(2805,1343)

119

ggT(1343,119)

34

ggT(119,34)

17

ggT(34,17)

0

¿ a2 mod b2 r ≠ 0 (Schritt 2)

>>>Das ist der ggT

ggT(29393, 2805) = 17

Lemma: Lemma von Bêzout a , b ∈ ℤ . Dann gibt es ggT (a , b)=x∗a+ y∗b

Seien

x , y ∈ℤ , so dass

Bemerkung: Die Zahlen x,y lassen sich leicht aus dem Euklidischen Algorithmus berechnen, wenn man in jedem

17.11.2020 Schritt bei der Berechnung von r = a mod b auch die Zahl m∈ ℕ mit a = m*b+r abspeichert (Siehe Beispiel m = grün mackiert). Dieses Verfahren nennt man auch erweiterter Euklidischer Algorithmus.

Beispiel: (ggT(29393, 2805) > fortgesetzt) Aus Beispiel Euklidischer Algorithmus folgt: Aus (3.4 [siehe Beispiel]) folgt

17=119 −3∗34 r=a3−3∗b3 Mit (3.3) erhält man

17=119 −3∗(1343−11∗119)=34∗119 −3∗1343 Mit (3.2) erhält man

17= 34∗(2805−2∗1343)−3∗1343= 34∗2805−71∗1343

|(Nichts ausmultiplizieren!)

und abschließend mit (3.1)

17= 34∗2805−71∗(29393−10∗2805 )=−71∗29393 + 744∗2805

|(x = -71; y = 744)

Kongruente Zahlen Satz: Modulo Rechnen Seine a , b ∈ ℤ und m ∈ ℕ . Dann gilt i) ( a+b ) mod m=(( a mod m)+(b mod m )) mod m ii) (a∗b)mod m=(( a mod m )( b mod m))mod m

| (( a mod m )( b mod m ))≫ Produkt der Reste

Beispiel:

Definition: kongruente Zahl Seien

a , b ∈ ℤ udn m ∈ ℕ . a und b heißen kongruent modulo m, falls sie bei Division

17.11.2020 durch m den gleichen Rest lassen, d.h. falls a mod m = b mod m. Man schreibt dafür , gesprochen ,, a kongruent b modulo m”.

Bemerkung: Mit der Notation aus Beispiel (siehe Woche zwei Beispiel: Restklasse) gilt also: a ☰ b mod m genau dann, wenn a,b in der gleichen Restklasse Rm enthalten sind.

Satz: Rechenregeln für Modulo-Rechnen a ☰ b mod mund c ☰ d mod m . Dann gilt a + c ☰(b+ d )mod m , a∗c ☰ (b∗d)mod m

Sei

Satz: Kleiner Satz von Fermat Sei p eine Primzahl und sei

a ∈ ℕ mit ggT(a,p) = 1. Dann ist

a

p −1

☰1 mod p

Folgerung: “Nicht-Prim-Test” Zum Testen, ob einen gegebene Zahl p∈ ℕ keine Primzahl ist, kann man wie folgt vorgehen: p−1 man sucht sich eine Zahl a mit ggT (a , p)=1 . Ist dann a❑ ≢1 mod ^p , dann ist nach dem Kleinen Satz von Fermat p keine Primzahl. p−1 Wenn p eine primzahl wären, müsste gelten a❑ ☰1 mod p ist zum Beispiel p ungerade, so kann man a = 2 wählen

Beispiel: p=27 ; a=2 . Nach Beispiel s.o. ist 226 ☰ 13 mod 27 und somit ist 27 keine Primzahl.

Notation: Sei

m∈ ℕ ,m ≥2

17.11.2020

m−1¿ m , } 1¿ m ,..... , ¿ i) Sei 0 ¿ m ,¿ ℤm={¿ die Menge der Restklasse bei Division durch m. ii) Auf der Menge

ℤm wird nun eine Addition

a∗b ¿m b ¿m :=¿ a ¿m⊙ ¿ a+b ¿ m und ¿ b ¿m :=¿ a ¿m⊕ ¿ ¿

|

⊕ und multiplikation

⊙ wie folgt definiert:

:=¿ per Definition

Bemerkung: Aufgrund von Satz: Rechenregel für Modulo-Rechnung sind

d ¿m b ¿m =¿ c ¿m , ¿ gilt a ¿m =¿ ¿ d ¿m c ¿m ⊙ ¿ b ¿m=¿ a ¿m ⊙¿ d ¿m und ¿ c ¿m ⊕ ¿ b ¿m=¿ a ¿m, ⊕ ¿ ¿ Also sind ⊙ und ⊕ Abbildungen von

⊙

und

⊕ wohldefiniert, d.h. für

ℤm × ℤm nach ℤm

Bemerkung: Seien

a ∈ ℤ, m∈ ℕ mit ggT (a , m)=1 . nach Lemma von Bêzout gibt es

Das ist äquivalent zu

1 ¿m x ¿m =¿ a ¿m ⊙ ¿ ¿

x , y ∈ℤ mit ax+my=1.

17.11.2020

Beispiel: Verknüpfungstafel für m =4

Bermerkung: i) sowohl bei

a ¿m 0 ¿m =¿ , a ¿m ⊕ ¿ ¿ und für jedes

0 ¿m a ' ¿m =¿ a ¿m⊕ ¿ ¿ ii) Für

ℤ (¿¿ 5 , ⊕) gilt ¿

a ¿m ∈ ℤm existiert ein ¿

a ' ¿m ∈ ℤm mit ¿

ℤ ℤ und (¿¿ 4 , ⊙) (¿¿ 5 , ⊙) gilt analog ¿ ¿

a ¿m 1 ¿m=¿ a ¿m ⊙ ¿ ¿ aber für

ℤ (¿¿ 4 , ⊕) als auch bei ¿

2 ¿4 ¿

1 ¿4 a ' ¿ 4=¿ gilt es kein Element in . 2¿ 4∗¿ ℤ4 mit ¿

17.11.2020

Für m =5 gibt es hingegen für jedes

1 ¿m a ' ¿m =¿ a ¿m⊙ ¿ ¿

¿ 0 ¿m } ein a ¿m ∈ ℤm {¿ ¿

a ' ¿m ∈ ℤm mit ¿...