Zahlentheorie¶
- 1. Teilbarkeit
- Modulo
- Teilbarkeit - Fortsetzung
1. Teilbarkeit¶
In diesem Abschnitt ist \(\mathbb{Z}\) die Grundmenge.
Definition 1: Teiler¶
Für zwi Zahlen \(m, n \in \gz\) mit \(m>0\) ist m Teiler n, falls es ein \(t\in \gz\) gibt, so dass \(n=t*m\). Kurzschreibweise: \(m\mid n\)
Spezialfälle:¶
\(1\mid n\), da \(n = n * 1\)
\(n\mid n\) für \(n > 0\), da \(n = 1 * n\) für \(n<0\) gilt das nicht, da lt. Definition 1: Teiler der \(Teiler>0\) sein muss.
\(m\mid 0\), da \(0=0*m\)
Definition 2: Teilermenge¶
Für eine Zahl \(n \in \gz\) ist \(T_n\) die Menge aller Teiler von \(n\). Also \(T_n = \{k>0 : k\mid n\}\)
Modulo¶
Ist m kein teiler von n, so bleibt bei der Division ein Rest. Für \(n,t,m,r \in \gz\) und \(m, r > 0\) können wir dann schreiben: \(n = t*m+r\). Dabei wählen wir t maximal, so dass \(t*m \le n\). Also \(t=\lfloor \frac{n}{m} \rfloor\). Eingesetzt \(n=\lfloor \frac{n}{m}\rfloor *m+r \Leftrightarrow r=n-\lfloor \frac{n}{m} \rfloor *m\). Da \(\lfloor \frac{n}{m} \rfloor *m \le n\), ist \(r\ge 0\). Andererseits ist \(r<m\), da \(\lfloor \frac{n}{m} \rfloor\) der größte Faktor ist. Somit ist \(t*m\le n \Rightarrow\) Es gilt: \(r \in \{0, 1, ..., m-1\}\)
Definition 3: Modulo¶
Die Menge der möglichen Reste ist \(Z_m=\{0,1,...,m-1\}\) Bei der ganzzahligen Division von n durch m bezeichnet man m als den underline{Modul} und den Rest r als n modulo m, kurz \(n \mod m\).
Folgerung 1:¶
Für \(n,m\in\gz\) mit \(m>0\) und \(r=n \mod m\)
Beweis:
Zu tun
Add Beweis
Eine Zahl n kann für feste m auf viele Arten in der Form \(n=t*m+r\) geschrieben werden. Beschränkt man r auf \(\{0,1,...,m-1\}\), dann gibt es nur noch eine Darstellung.
Teilbarkeit - Fortsetzung¶
Definition 4: Schnittmenge von Teilmengen¶
Für zwei Zahlen \(m,n\in\gz\) ist \(T_{m,n}=T_m \cap T_n\)
Definition 5: Größter gemeinsamer Teiler (ggT)¶
Für zwei Zahlen \(m,n\in\gz\) mit \(m,n\ne0\) ist der größte gemeinsame Teiler, kurz ggT(m,n), die größte Zahl in \(T_{m,n}\). Also \(max(T_{m,n})\)
Formal:
Definition 6: Kleinstes gemeinsames Vielfaches (kgV)¶
Das kleinste gemeinsame Vielfache von \(m,n\in\gz\) mit \(m,n>\) ist die kleinste Zahl, die von m und n geteilt wird.
Formal:
Lemma 1:¶
Für alle \(a,b\in\gz\) ist \(T_{m,n}\subseteq T_{a*m+b*n}\)
Beweis:¶
Sei \(k\in T_{m,n}\) ein beliebiger Teiler von m und n. D.h. es gibt \(s,t\in\gz\), so dass \(m=s*k\) und \(n=t*k\). Dann gilt: \(a*m+b*n = a*s*k+b*t*k = k*(a*s+b*t)\). Folglich gilt: \(k \mid (a*m+b*n)\).
Spezialfall:¶
Für den ggT: \(ggT(m,n)\mid (a*m+b*n)\).
Beispiel:¶
\(\Rightarrow\) Teilmenge \(T_{a*m+b*n}\) enthält im allgemeinen mehr Zahlen als \(T_{m,n}\). Es wäre jedoch von Vorteil, mindestens eine der Zahlen m, n zu verkleinern, ohne \(T_{m,n}\) zu verkleinern.
Folgerung 2:¶
Für alle \(a\in\gz\) ist \(T_{m,n} = T_{m,n-a*m}\)
Zu tun
Beweis: \(T_{m,n} \subseteq T_{m,n-a*m}\)
Beispiel:¶
Zu tun
Beweis: \(T_{m,n} \supseteq T_{m,n-a*m}\)
Wählt man in Folgerung 2: \(a\ge 1\), so verkleinert sich das Zahlenpaar \((m,n)\) zu \((m,n-a*m)\). Trotzdem bleiben die gemeinsamen Teiler die selben. Je kleiner das Zahlenpaar \((m,n-a*m)\) wird, desto einfacher kann der ggT bestimmt werden. Folglich wählen wir a maximal, so dass \(n-a*m \ge 0\) ist.
Folgerung 2: (\(T_{m,n} = T_{m,n-a*m})\) gilt unter anderem für \(a=\lfloor \frac{n}{m} \rfloor\) (da \(\lfloor \frac{n}{m} \rfloor * m \le n\), deshalb wird a maximal). Eingesetzt: \(n-a*m=n-\lfloor \frac{n}{m} \rfloor *m = n \mod m\).
Folgerung 3:¶
Für \(m>0\) gilt: \(T_{m,n}=t_{m,n\mod m}\)
Euklidischer Algorithmus¶
Rekursive Formulierung:¶
Euklid(m,n)
if m=0 then
return n
else
return Euklid(n mod m, m)
Iterative Formulierung:¶
Euklid(m,n)
while m>0 do
r <- n mod m
n <- m
m <- r
return n
Folgerung 4:¶
\(T_{m,n}=T_{ggT(m,n)}\). D.h. jeder gemeinsamer Teiler von n und m teilt folglich auch den ggT(m,n).
Beispiel: Euklidiescher Algorithmus - kürzen von Brüchen¶
\(\frac{233408}{344512}\) soll auf die kleinstmögliche Form gekürzt werden.
| i | \(n_i\) | Berechnung: \(m_i\) | \(m_i\) |
|---|---|---|---|
| 0 | 344512 | 233408 | |
| 1 | 233407 | \(344512 \mod 233408\) | = 111104 |
| 2 | 111104 | \(233407 \mod 111104\) | = 11200 |
| 3 | 11200 | \(111104 \mod 11200\) | = 896 |
| 4 | 896 | \(11200 \mod 896\) | = 448 |
| 5 | 448 | \(896 \mod 448\) | = 0 |
\(\Rightarrow ggT(233408, 344512)=448\)
\(\Rightarrow \frac{233408}{344512} = \frac{\frac{233408}{448}}{\frac{344512}{448}} = \frac{512}{729}\)
Erweiterter Euklidischer Algorithmus¶
EuklidErweitert(m,n)
if m = 0 then
return (n, 0, 1)
else
(d, b', a') <- EuklidErweitert(n mod m, m)
a <- a' - b'(n div m)
b <- b'
return (d, a, b)
