Abschnitt 26

Modulare Arithmetik

mittelviz

a \equiv b (mod n) ⟺ n ∣ (a - b)

Definiert die Gleichheit der Residuen modulo n.

mittelviz

a \equiv b, c \equiv d (mod n) \Rightarrow a + c \equiv b + d, a c \equiv b d (mod n)

Kongruenzen bleiben unter Summe und Produkt erhalten.

mittelviz

a a^{- 1} \equiv 1 (mod n) ⟺ g cd (a, n) = 1

Die Umkehrung liegt genau dann vor, wenn a und n teilerfremd sind.

mittel

a x + b y = g cd (a, b)

Verbinden Sie den größten gemeinsamen Faktor mit ganzzahligen Linearkombinationen.

fortgeschrittenviz

x \equiv a_{i} (mod n_{i}); N = i \prod n_{i}

Systeme mit Koprime-Modulen haben eine eindeutige Lösung modulo N.

fortgeschrittenviz

a^{p - 1} \equiv 1 (mod p) (p ∤ a)

Zentrales Ergebnis für modulare Arithmetik und Kryptographie.