Zum Inhalt

Zahlentheorie

In der Zahlentheorie, neben der Geometrie der älteste Teil der Mathematik, geht es v.a. um natürliche und ganze Zahlen. Man sucht z.B. schon lange pythagoräische Tripel, ganze Zahlen, die die Gleichung $ x^2+y^2=z^2 $ lösen und nach wie vor aktuell ist die Suche nach Primzahlen. Die bekanntesten Mathematiker in diesem Gebiet heißen Gauß und Euler.

Im Folgenden bedeuten griechische Variablen reelle Zahlen, alle anderen Variablen sind, wenn nicht anders angegeben, ganze Zahlen.

Literatur:

  • G.H. Hardy, E.M. Wright: An Indroduction to the Theory of Numbers. Oxford, Clarendon
  • Loo–Keng Hua: Introduction to Number Theory. Springer Verlag.
  • Skript von Wolke aus Freiburg 2005

Teilbarkeit

Bei die Multiplikation ist bei ganzen Zahlen nicht immer invertierbar, daher sind die ganzen Zahlen bezüglich der Multiplikation nur Halbgruppen.

Es folgen erst ein mal ein paar wichtige Definitionen und Folgerungen.

Wenn man eine ganze Zahl $ b $ durch eine andere ganze Zahl $ a $ restlos teilen kann, sagt man $ a $ teilt $ b $, $ a $ ist Teiler von $ b $, $ b $ wird von $ a $ geteilt bzw. $ b $ ist Vielfaches von $ a $ und schreibt $ a|b $.

Teilbar

a|b \Leftrightarrow \exists c \text{ sodass } b= ac

Wahr oder unwahr?

a) $ 1|5 $

b) $ 5|5 $

c) $ 2|5 $

d) $ -2 |5 $

e) $ 0|0 $

f) $ 0|a $

Lösung

unwahr sind c) und f).

Beweise

a) $ a|b \Rightarrow \forall c : a|bc $

b) $ a|b \land b|c \Rightarrow a|c $

c) $ a|b \land a|c \Rightarrow a|xb+yc \forall x,y $

d) $ a|b \land b|a \Rightarrow |a| = |b| $

e) $ a|b \Rightarrow \forall c: ca|cb $

Lösung

Beim Beweis von d) darf man nicht durch $ 0 $ teilen, also braucht man eine Fallunterscheidung.

Außerdem braucht man manchmal die Gauß-Klammer, die das größte Ganze angibt, also die zur ganzen Zahl abgerundete Zahl. Zum Beispiel $ [\pi] = \lfloor \pi \rfloor = 3 $ , $ [-2,1] = -3 $ .

Gauß-Klammer

[\alpha] = \max\{a, a \leq \alpha\}

Wie man den gemeinsamen Teiler $ d $ von $ a $ und $ b $ definiert ist klar.

Lösung

$ \land $

Damit ergibt sich also für den größten gemeinsamen Teiler bzw. ggT?

Lösung

$ \max $

ggT

Den ggT $ d $ zweier Zahlen $ a $ und $ b $ schreiben wir

d = (a,b)

Teilerfremd

Zwei Zahlen $ a $ und $ b $ heißen teilerfremd oder relativ prim, wenn (a,b) = 1.

Beispiele

Was bedeuten die Zahlen und was bedeutet das für die paarweise Teilerfremdheit?

a) $ (6,10,15) $

b) $ (6,10) $

c) $ (6,15) $

d) $ (10,15) $

Lösung

1, 2, 3, 5.

Also folgt aus der paarweisen Teilerfremdheit die Teilerfremdheit einer Liste, aber nicht umgekehrt.

Primzahlen

$ p $ heißt Primzahl, wenn $ p > 1 $ und nur $ 1|p \land p|p$.

Alle anderen Zahlen heißen zusammengesetzt.

Kennt jeder das Sieb des Eratosthenes?

Folgerung

Für Primzahlen p gilt: $ p|ab \Rightarrow p|a \lor p|b $.

Beweis

$ d=(p,a) $. Falls $ d>1 $, muss $ d=p $ sein, also $ p|a $. Falls $ d=1 $ folgt $ p|b $ da $ c|ab \land (c,b)=1 \Rightarrow c|a $.

Satz von Euklid

Es existieren unendlich viele Primzahlen.

Beweis

Euklid führte einen Beweis durch Widerspruch.

Ein Primteiler ist ein Teiler, der eine Primzahl ist. Jede Zahl $ m >1 $ besitzt einen Primteiler ($ d $ mit $ 1 < d \leq n \land d|n $).

Angenommen es gibt nur endlich viele Primzahlen: $ k $ viele.

$ n = p_1 \cdot ... \cdot p_k $ hat dann $ k $ Primteiler.

Wenn $ m = n+1 $ eine Primzahl ist, haben wir einen Widerspruch zur Annahme.

Wenn $ m = n+1 $ keine Primzahl ist, muss $ m $ einen Primteiler $ d $ besitzen, der von den bisherigen $ k $ Primteilern verschieden ist. Denn (Widerspruchgsbeweis im Widerspruchsbeweis) wenn $ d|m \land d = p_i (1\leq i \leq k) \Rightarrow d|1$, was laut Definition des Primteilers nicht sein kann.

Euklids Beweis

Satz von Gauß

Für jede natürliche Zahl existiert eine eindeutige Primfaktorzerlegung.