Satz1: Division mit Rest
SInd c und d ganze Zahlen, wobei d ungleich 0, dann existieren eindeutige ganze Zahlen q und r, so dass
c=q*d+r und
0</=r</d/.
Sind c und d natürliche Zahlen, so ist auch q eine natürliche Zahl oder 0.

Satz2: Eigenschaften der Teilbarkeitsrelation

• Für alle ganzen Zahlen a,b und c gilt: Aus a|b und b|c folgt a|c. (Transitivität)
• Für alle ganzen Zahlen a e Z gilt a|a.
• Für alle ganzen Zahlen a und b gilt a|b und b|a genau dann, wenn |a|=|b|.
• Für alle ganzen Zahlen a und b gilt a|b genau dann, wenn a|-b.

Definition: a|b = a ist Teiler von b
a|b = Es existiert ein q, das eine ganze Zahl ist, so dass gilt b=q*a

bild einfügen von mathematischen allaussagen!!

Definition: Sei T(a) die Menge aller Teiler von a und T(b) die Menge aller Teiler von b, so bezeichnen wir deren Schnittmenge als T(a,b), also die Menge der gemeinsamen Teiler von a und b. Das größte Element dieser Menge nennen wir größter gemeinsamer teiler von a und b, also ggT (a,b)

Proposition3:
Seinen a,b,c und d ganze Zahlen, wobei wir d unglich 0 annehmen. Außerdem soll a=b+c gelten.
Ist d ein Teiler von b, so tritt bei der Division mit Rest von a durch d derselbe Rest auf wie bei der Division mit Rest von c durch d.

Folgerung4:
Wir betrachten dieselben Voraussetzungen wie in der Proposition, das heißt, a,b, c und d sind ganze Zahlen und d ist ungleich 0, d|b und a=b+c. In dieser Situation ist d genau dann ein Teiler von a, wenn d ein Teiler von c ist.

Proposition5: Teilbarkeit durch 10

• Eine ganze Zahl ist genau dann durch 10 teilbar, wenn ihre Dezimaldarstellung mit der Ziffer 0 endet.

Proposition6: Teilbarkeit durch 5/2

• Eine ganze Zahl ist genau dann durch 5 teilbar, wenn ihre Dezimaldarstellung mit einer der Ziffern 0 oder 5 endet.
• Eine ganze Zahl ist genau dann durch 5 teilbar, wenn ihre Dezimaldarstellung mit einer der Ziffern 0,2,4,6 oder 8 endet.

Proposition7: Teilbarkeit durch 100

• Eine ganze Zahl ist genau dann durch 100 teilbar, wenn ihr Dezimaldarstellung mit den Ziffern 00 endet.

Proposition8: Teilbarkeit durch 3/9

• Eine ganze Zahl ist genau dann durch 3 teilbar, wenn ihre Quersumme durch 3 teilbar ist.
• Eine ganze Zahl ist genau dann durch 9 teilbar, wenn ihre Quersumme durch 9 teilbar ist.

Definition: diophantische Gleichungen haben zwei Variablen. Sie sind am einfachsten, wenn die beiden unbekannten jeweils linear vorkommen. Beispiel: 16=7x+6y

Proposition9:
Ist t ein gemeinsamer Teile der ganzen zahlen a und b, so teilt t für beliebige ganze Zahlen x und y auch den Ausdruck: xa+yb

Satz10:
Ist g e Z der größte gemeinsame Teiler von a und b, so gibt es ganze Zahlen x0 und y0 mit g=x0a + y0b.

Satz11: Lösbarkeit linearer diophantischer Gleichungen
Seien a, b und c ganze Zahlen. Die Gleichung
ax+by=c
besitzt genau eine ganzzahlige Lösung (x1,y1), wenn die Zahl c durch den größten gemeinsamen Teiler von a und b teilbar ist.

Proposition12:
Der größte gemeinsame teiler von a und b ist die kleinste natürliche Zahl, die sich in der Form
xa+yb
mit ganzen zahlen x und y schreiben lässt.

Folgerung13:
Sind a und b ganze zahlen und m eine natürliche Zahl, so gilt
ggT(ma,mb) = m*ggT(a,b).

Folgerung14:
Wir nehmen an, dass a und b von Null verschiedene ganze Zahlen und c eine natürliche Zahl ist. Ist a ein Teiler des Produktes b*c und gilt ggT(a,b)=1, so ist a ein Teiler von c.

Proposition15:
Sind a und b zwei ganze Zahlen, die nicht beide Null sind, dann teilt jeder gemeinsame Teiler von a und b auch den größten gemeinsamen Teiler ggT(a,b).

Satz16: Euklidischer Algorythmus
Gegeben seien zwei natürliche Zahlen a und b. Dann gilt:

• Ist a ein teiler von b, so gilt ggT(a,b) = a.
• Ist a kein Teiler von b, so führen wir eine Folge von Divisionen mit Rest durch:
  
  

b= q1 a + r1 ( -> 0< r1 < a)
a= q2 r1 + r2 ( -> 0< r2 < r1)
r1= q3 * r2 +r3 (-> 0< r3 < r2)

(...)

rk-3 = qk-1 rk-2 + rk-1 (-> 0< rk-1< rk-2)
rk-2 = qk rk-1 + rk (-> 0< rk < rk-1)
rk-1 = qk+1 * rk

Die Zahl k>/=1 ist dadurch bestimmt. dass rk der letzte von 0 verschiedene Rest ist. Dieser Rest rk ist der größte gemeinsame Teiler von a und b.
Man erhält die ganzen zahlen x und y mit
ggT (a,b) = rk = xa + yb
indem man die Reste ri für i e {1,2, ..., k} nacheinander jeweils mit Hilfe der Gleichungen als Linearkombinationen von a und b schreibt.

Proposition17: Das kleinste gemeinsame Vielfache
Das kleinste gemeinsame Vielfache kgV(a,b) zweier von 0 verschiedener ganzer Zahlen a und b ist ein Teiler jedes gemeinsamen Vielfachen von a und b.
Die Menge der gemeinsamen Vielfachen von a und b besteht also genau aus den ganzzahligen Vielfachen von kgV(a,b), das heißt aus den Zahlen:
{0 ; +/- kgV(a,b) ; +/- 2kgV(a,b) ; +/- 3kgV(a,b) ; ...}

Beispiel: Die Menge aller gemeinsamen Vielfachen von 12 und 20 besteht aus den Zahlen:

..., -240, -180, -120, -60, 0, 60, 120, 180, 240, ...
Dies sind gerade die ganzzahligen Vielfachen von 60 = kgV(12,20)

so funktionierts

Satz19: Lösungsmenge einer diophantischen Gleichung
Für die ganzzahligen Koeffizienten a,b und c der diophantischen Gleichung ax+by=c gelte ggT(a,b)|c, so dass die Gleichung ganzzahlige Lösungen besitzt.
Ist eine beliebige spezielle Lösung (x1,y1) bekannt, so erhält man die vollständige Menge aller ganzzahligen Lösungen als

L= {(x1+b/g·n,y1−a/g·n) : n∈Z},

wobei g= ggT(a,b) der größte gemeinsame Teiler von a und b ist.

Definition: EinePrimzahl ist eine natürliche Zahl p >1, welche sich nicht als Produkt aus kleineren natürlichen Zahlen schreiben lässt.

Proposition20:
Für jede natürliche Zahl n >1 ist der kleinste Teiler d, der größer als1 ist, eine Primzahl.

Proposition22:
In der Liste der Primzahlen gibt es beliebig lange Lücken, d.h. zu jeder natürlichen Zahl n gibt es n aufeinander folgende natürliche Zahlen, die keine Primzahlen sind.

Satz23: Hauptsatz der elementaren Arithmetik
Die Primfaktorzerlegung jeder natürlichen Zahl n >1ist bis auf die Reihenfolge der Faktoren eindeutig.