Formelsammlung – Zahlen SoSe 25

Übung 1

Begründungsformen

3 Ebenen: Zahlenbeispiel → Anschauung → algebraischer Beweis
Struktur: Voraussetzung | Behauptung | Begründung
Muster 1: $n + (n+1) = 2n+1$ (ungerade)
Muster 2: $n^2 - (n-1)(n+1) = 1$
Muster 3: $n(n{+}1)-(n{-}1)n = 2n$ (Doppelte der mittleren Zahl)

Übung 2

Teilbarkeit

Definition: $a \mid b \;\Leftrightarrow\; \exists k \in \mathbb{N}: b = a \cdot k$
Summenregel:
$a\mid b \;\wedge\; a\mid c \;\Rightarrow\; a\mid(b+c)$
Differenzregel (für $b > c$):
$a\mid b \;\wedge\; a\mid c \;\Rightarrow\; a\mid(b-c)$
Produktregel:
$a\mid b \;\Rightarrow\; a\mid(n \cdot b)$
Beweis immer: $b=a\cdot k_1$, $c=a\cdot k_2$ einsetzen, ausklammern.

Übung 3

Primzahlen

Definition: $p > 1$, nur durch $1$ und $p$ teilbar
Primzahlentest:
Teste nur Primzahlen $p \leq \lfloor\sqrt{n}\rfloor$.
Wenn kein $p$ teilt → $n$ prim.
Primzahlenlücken:
$H = n!$: dann sind $H+2, H+3, \ldots, H+n$
alle zusammengesetzt (Lücke der Länge $n-1$).

Übung 4

Primfaktorzerlegung

PFZ: $n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_r^{e_r}$ (eindeutig)
$\text{ggT}$: Minimum der Exponenten; $\;\text{kgV}$: Maximum
$\text{ggT}(a,b)\cdot\text{kgV}(a,b) = a\cdot b$
Potenzgesetze:
G1: $a^m \cdot a^n = a^{m+n}$
G2: $a^m \div a^n = a^{m-n}$ $(m\geq n)$
G3: $(a^m)^n = a^{m\cdot n}$
G4: $(a\cdot b)^n = a^n \cdot b^n$
G5: $a^0 = 1$
Wer zerlegt zuletzt? Immer $\Omega(n)-1$ Schritte.
Quadratzahl: alle $e_i$ gerade. Kubikzahl: alle $e_i$ durch 3 teilbar.

Übung 5

Teiler

Teilermenge: $T(n) = \{t \in \mathbb{N} : t \mid n\}$
Vielfachenmenge: $V(n) = \{k \cdot n : k \in \mathbb{N}\}$
$\text{ggT}(a,b) = \max(T(a)\cap T(b))$
$\text{kgV}(a,b) = \min(V(a)\cap V(b))$
Teileranzahl $\tau(n)$:
$n = p_1^{e_1}\cdots p_r^{e_r}$
$\tau(n) = (e_1+1)(e_2+1)\cdots(e_r+1)$
Malhäuser: Stockwerke = Primfaktoren mit Vielfachheit ($\Omega(n)$).
Hasse-Diagramm: Teiler als Punkte, Kante $t_1 \to t_2$ wenn $t_1 \mid t_2$ ohne Zwischenstufe.

Übung 6

ggT, kgV & Hasse

Euklid:
$\text{ggT}(a,b) = \text{ggT}(b,\; a \bmod b)$
Abbruch wenn Rest $= 0$, letzter $\neq 0$ ist ggT.
Über PFZ:
$\text{ggT}$: $\min$ der Exponenten
$\text{kgV}$: $\max$ der Exponenten
$\text{ggT}(a,b)\cdot\text{kgV}(a,b) = a \cdot b$
Hasse-Diagramm mehrerer Zahlen:
ggT = kleinstes gemeinsames Element von unten,
kgV = kleinstes gemeinsames Element von oben.

Übung 7

Diophantische Gleichungen

Form: $a\cdot x + b\cdot y = c$, $\;x,y \in \mathbb{Z}$
Lösbar $\Leftrightarrow$ $\text{ggT}(a,b) \mid c$
Vorgehen:
1. $d = \text{ggT}(a,b)$ per Euklid
2. $d \mid c$? Wenn nein: unlösbar.
3. Rückwärts-Einsetzen → Partikularlösung $(x_0, y_0)$
4. Lösungsmenge: $x = x_0 + \tfrac{b}{d}\cdot t,\quad y = y_0 - \tfrac{a}{d}\cdot t,\quad t\in\mathbb{Z}$

Übung 8

Kongruenzen

4 Charakterisierungen ($a \equiv b \pmod{m}$):
(1) $m \mid (a-b)$
(2) $a \bmod m = b \bmod m$
(3) $\exists k\in\mathbb{Z}: a = b + k\cdot m$
(4) gleicher Rest bei Division durch $m$
Seien $a\equiv b$, $c\equiv d \pmod m$:
Add.: $a+c \equiv b+d$
Mul.: $a\cdot c \equiv b\cdot d$
Sub.: $a-c \equiv b-d$
NIM ($k$ = max. Züge pro Zug):
Verlierer: $n \equiv 0 \pmod{k+1}$ (2. Spieler gewinnt)
Gewinner: $n \not\equiv 0 \pmod{k+1}$ (1. Spieler gewinnt)
Strategie: immer auf nächstes $k{+}1$-Vielfaches bringen.

Übung 9

Restklassenarithmetik

Restklasse: $[a]_m = \{x\in\mathbb{Z} : x\equiv a\pmod m\}$
Ring: $R_m = \{[0]_m, [1]_m, \ldots, [m{-}1]_m\}$
Mult. Inverses:
$[b]_m$ ist Inverses von $[a]_m \;\Leftrightarrow\; [a]_m \odot [b]_m = [1]_m$
Existiert $\Leftrightarrow\; \text{ggT}(a,m) = 1$
Finden: per Tafel ablesen, oder dioph. Gleichung $a\cdot b \equiv 1 \pmod m$
Additives Inverses:
$[-a]_m = [m-a]_m$ — existiert immer in $R_m$
Zyklus von $[a]_m$:
Länge $l = \dfrac{m}{\text{ggT}(a,m)}$

Übung 10

Kongruenzgleichungen

Phi-Funktion $\varphi(m)$:
$\varphi(p) = p-1$
$\varphi(p^k) = p^{k-1}(p-1)$
$\varphi(a\cdot b) = \varphi(a)\cdot\varphi(b)$ falls $\text{ggT}(a,b)=1$
$a\cdot x \equiv b \pmod{m}$:
Sei $d = \text{ggT}(a,m)$.
$d \nmid b$: keine Lösung
$d \mid b$, $d=1$: genau 1 Lösung $\bmod m$
$d \mid b$, $d>1$: genau $d$ Lösungen $\bmod m$
3 Lösungsstrategien:
S1 – Probieren: alle $x \in \{0,\ldots,m{-}1\}$ testen
S2 – Kürzen: durch $d$ dividieren: $\tfrac{a}{d}x \equiv \tfrac{b}{d}\pmod{\tfrac{m}{d}}$
S3 – Dioph. Gl.: $ax - km = b$, erw. Euklid
System ($\text{ggT}(m_1,m_2)=1$):
$x\equiv a_1\pmod{m_1}$, $x\equiv a_2\pmod{m_2}$
→ eindeutige Lösung $\bmod m_1\cdot m_2$ (Chin. Restsatz)

Übung 11

RSA-Algorithmus

Schlüsselerzeugung:
Wähle Primzahlen $p \neq q$
$n = p \cdot q$
$\varphi(n) = (p-1)(q-1)$
$e$: beliebig mit $\text{ggT}(e,\varphi(n)) = 1$
$d$: $e \cdot d \equiv 1 \pmod{\varphi(n)}$ (via dioph. Gl.)
Ver-/Entschlüsseln:
Verschlüsseln: $c \equiv m^e \pmod{n}$
Entschlüsseln: $m \equiv c^d \pmod{n}$
Öffentlich: $(n, e)$ | Privat: $d$ (und $p,q,\varphi(n)$)
Sicherheit: Faktorisierung von $n$ schwer für große $n$.

Kurzreferenz

Euklidischer Algorithmus & Rückwärtseinsetzen

Vorwärts (ggT finden):

ggT(252, 105):
252 = 2·105 + 42
105 = 2·42 + 21
42 = 2·21 + 0
⟹ ggT = 21

Rückwärts (Darstellung als Linearkombination):

21 = 105 − 2·42
= 105 − 2·(252 − 2·105)
= 5·105 − 2·252
⟹ 21 = 5·105 + (−2)·252

Für dioph. Gleichung $252x + 105y = 21$: Partikularlösung $x_0 = -2,\; y_0 = 5$. Allg. Lösung: $x = -2 + \tfrac{105}{21}\cdot t = -2+5t$, $\; y = 5 - \tfrac{252}{21}\cdot t = 5-12t$, $\; t\in\mathbb{Z}$.

Schnell-Check

Häufige Formeln auf einen Blick

Teileranzahl

$\tau(n) = \prod_{i}(e_i+1)$

z.B. $\tau(12)=\tau(2^2\cdot3)=3\cdot2=6$

Phi-Funktion

$\varphi(p^k)=p^{k-1}(p-1)$

z.B. $\varphi(8)=\varphi(2^3)=4$

ggT · kgV

$\text{ggT}\cdot\text{kgV} = a\cdot b$

nur für 2 Zahlen!

RSA: Schlüssel-Check

$e\cdot d \equiv 1 \pmod{\varphi(n)}$

$d$ per erw. Euklid aus $e$

Kongruenzgl. lösbar?

$\text{ggT}(a,m) \mid b$

sonst: keine Lösung

Dioph. Gl. lösbar?

$\text{ggT}(a,b) \mid c$

$ax+by=c$

Quadratzahl-Check

alle $e_i$ gerade

via PFZ prüfen

Inverses existiert?

$\text{ggT}(a,m) = 1$

$[a]_m$ in $R_m$

Zahlen SoSe 25 – Alle Formeln & Regeln