Einführung in die Zahlentheorie

Einführung in die Zahlentheorie

Teilbarkeit

Teilbarkeit

Eigenschaften der Teilbarkeit

Teilungsalgorithmus

Teilungsalgorithmus für negative $a$

Euklidischer Algorithmus

Größter Gemeinsamer Teiler ( $ggT$ )

Alternative Definition des $ggT$

$ggT$ und „relativ prim“

Berechnung des ggT von zwei Zahlen a und b mit Hilfe des euklidischen Algorithmus

Beispiel für die Berechnung des $ggT$ ( $ggT(710,310)$ ) mit Hilfe des euklidischen Algorithmus

Euklidischer Algorithmus

Modulare Arithmetik

Der Modulus

Modulare Arithmetik (kongruent modulo $n$ )

Eigenschaften der Kongruenz

$a \equiv b \pmod{n}$ wenn $n|(a-b)$ — Erklärt

Eigenschaften der modularen Arithmetik

$[(a \bmod n) + (b \bmod n)] \bmod n = (a + b) \bmod n$ — Erklärt

Modulare Arithmetik (Beispiele für Eigenschaften)

Rechnung Modulo 8

Additive und Multiplikative Inverse Modulo 8

Eigenschaften der modularen Arithmetik für ganze Zahlen in $Z_n$

Euklidischer Algorithmus - neu betrachtet

Erweiterter Euklidischer Algorithmus

$ggT(a=42,b=30)$ mit erweitertem Euklidischen Algorithmus

Erweiterter Euklidischer Algorithmus - Systematische Berechnung für $ggT(710,310)$

Erweiterter Euklidischer Algorithmus - Formeln

Erweiterter Euklidischer Algorithmus

Erweiterter Euklidischer Algorithmus - Beispiel $ggT(1759,550)$

Primzahlen und Primzahlenbestimmung

Primzahlen

Fermats (kleines) Theorem

Die Eulersche Totientenfunktion $\phi(n)$

Eulers Theorem

Miller-Rabin-Primzahltest

Deterministische Primzahltests

Übung

Übung

Einführung in die Zahlentheorie

Teilbarkeit

Teilbarkeit

Eigenschaften der Teilbarkeit

Teilungsalgorithmus

Teilungsalgorithmus für negative aaa

Euklidischer Algorithmus

Größter Gemeinsamer Teiler (ggTggTggT)

Alternative Definition des ggTggTggT

ggTggTggT und „relativ prim“

Berechnung des ggT von zwei Zahlen a und b mit Hilfe des euklidischen Algorithmus

Beispiel für die Berechnung des ggTggTggT (ggT(710,310)ggT(710,310)ggT(710,310)) mit Hilfe des euklidischen Algorithmus

Euklidischer Algorithmus

Modulare Arithmetik

Der Modulus

Modulare Arithmetik (kongruent modulo nnn)

Eigenschaften der Kongruenz

a≡b(modn)a \equiv b \pmod{n}a≡b(modn) wenn n∣(a−b)n|(a-b)n∣(a−b) — Erklärt

Eigenschaften der modularen Arithmetik

[(a mod n)+(b mod n)] mod n=(a+b) mod n[(a \bmod n) + (b \bmod n)] \bmod n = (a + b) \bmod n[(amodn)+(bmodn)]modn=(a+b)modn — Erklärt

Modulare Arithmetik (Beispiele für Eigenschaften)

Rechnung Modulo 8

Additive und Multiplikative Inverse Modulo 8

Eigenschaften der modularen Arithmetik für ganze Zahlen in ZnZ_nZn​

Euklidischer Algorithmus - neu betrachtet

Erweiterter Euklidischer Algorithmus

ggT(a=42,b=30)ggT(a=42,b=30)ggT(a=42,b=30) mit erweitertem Euklidischen Algorithmus

Erweiterter Euklidischer Algorithmus - Systematische Berechnung für ggT(710,310)ggT(710,310)ggT(710,310)

Erweiterter Euklidischer Algorithmus - Formeln

Erweiterter Euklidischer Algorithmus

Erweiterter Euklidischer Algorithmus - Beispiel ggT(1759,550)ggT(1759,550)ggT(1759,550)

Primzahlen und Primzahlenbestimmung

Primzahlen

Fermats (kleines) Theorem

Die Eulersche Totientenfunktion ϕ(n)\phi(n)ϕ(n)

Eulers Theorem

Miller-Rabin-Primzahltest

Deterministische Primzahltests

Übung

Übung

Teilungsalgorithmus für negative $a$

Größter Gemeinsamer Teiler ( $ggT$ )

Alternative Definition des $ggT$

$ggT$ und „relativ prim“

Beispiel für die Berechnung des $ggT$ ( $ggT(710,310)$ ) mit Hilfe des euklidischen Algorithmus

Modulare Arithmetik (kongruent modulo $n$ )

$a \equiv b \pmod{n}$ wenn $n|(a-b)$ — Erklärt

$[(a \bmod n) + (b \bmod n)] \bmod n = (a + b) \bmod n$ — Erklärt

Eigenschaften der modularen Arithmetik für ganze Zahlen in $Z_n$

$ggT(a=42,b=30)$ mit erweitertem Euklidischen Algorithmus

Erweiterter Euklidischer Algorithmus - Systematische Berechnung für $ggT(710,310)$

Erweiterter Euklidischer Algorithmus - Beispiel $ggT(1759,550)$

Die Eulersche Totientenfunktion $\phi(n)$