Zahlentheorie

aus www.iwiki.de, der freien Wissensdatenbank

Inhaltsverzeichnis

1 Elementare Zahlentheorie

Elementare Zahlentheorie

Die elementare Zahlentheorie kommt ohne die Hilfsmittel anderer mathematischer Teilgebiete aus.

Teilbarkeit

Unter Teilbarkeit versteht man die Division von ganzen Zahlen. Eine ganze Zahl ist somit teilbar, wenn bei der Division kein Rest verbleibt.

Sind $a, b \in Z$ und ist $b \not= 0$ , so heißt a durch b teilbar (b teilt a), wenn es eine ganze Zahl q gibt, so dass a = bq ist.

[bearbeiten]

Teilbarkeitsregeln

Gilt c|b und b|a, so gilt auch c|a

[bearbeiten]

Beispiel

3|6 und 6|18 -> 3|18

[bearbeiten]

Teilen mit Rest

Bei Teilen mit Rest wiederum bleibt bei der Division ein Rest (r) übrig.

Für zwei ganze Zahlen a,b mit b $\not=$ 0 gibt es nur folgende Darstellung:

a = bq + r mit q, r $\in Z$ und 0 $\le r$ < b,falls b > 0 und 0 $\le$ r < -b, falls b < 0.

a heisst Dividend
b Divisor
q Quotient
r Rest der Division von a durch b
q mit a|b
und r mit a modulo b

[bearbeiten]

Der größte gemeinsame Teiler (ggT)

Für zwei ganze Zahlen a und b, die nicht beide null sind, gibt es stets einen größten gemeinsamen Teiler (ggT). Dies bedeutet die größte natürliche Zahl, durch die a und b ohne Rest teilbar sind.

D = ggT(a,b) (d ist größter gemeinsamer Teiler von a und b)

[bearbeiten]

Der Euklidische Algorithmus

Der euklidische Algorithmus ist nach dem griechischen Mathematiker Euklid benannt. Hierbei handelt es sich um einen Rechenalgorithmus der als Ergebnis den größten gemeinsamen Teiler zweier natürlicher Zahlen berechnet.

Ist $a,b \in Z$ und $a,b \not= 0$ , dann gibt es genau einen positiven größten gemeinsamen Teiler d von a und b -> d = ggT(a,b)

ggT(a,b) = ggT (a mod b, b) = ggT (b, a mod b)

Dieses Resultat wird wiederholt angewendet bis die Reste immer kleiner werden und schließlich sogar Null sind.

[bearbeiten]

Algorithmus

INPUT: a,b $/ i n$ $\mathbb{N}_0$ mit $a \ge b$ .

OUTPUT: ggT(a,b).

WHILE b /not 0 DO:
1. r: = a mod b.
2. a:= b.
3. b:= r.
RETURN a.

[bearbeiten]

Der erweiterte Euklidische Algorithmus

Der Euklidische Algorithmus kann erweitert werden, um nicht nur den ggT(a,b) zweier natürlicher Zahlen a und b zu berechnen sondern, noch zwei ganze Zahlen die folgende Eigenschaft

x*a + y*b = ggT(a,b)

zu bestimmen.

[bearbeiten]

Teilerfremde Zahlen und das kleinstes gemeinsames Vielfaches (kgV)

Man spricht von Teilerfremdheit wenn bei der Primfaktorzerlegung kein gemeinsamer Faktor vorkommt.

ggT(a,b) = 1

Das kleinste gemeinsame Vielfaches (kgV) beschreibt die größte natürliche Zahl, durch die sowohl a als auch b ohne Rest teilbar sind.

Sind a und b nicht null ist ein kleinstes gemeinsames Vielfaches (a,b) möglich. Hierbei ergibt sich eine kleinste positive Zahl, die sowohl Vielfaches von a als auch Vielfaches von b ist.

[bearbeiten]

Primzahlen und Primfaktorzerlegungen

Eine Zahl mit p > 1 heißt Primzahl, wenn sie in N außer 1 und p keine weiteren Teiler hat. Eine Primzahl ist eine natürliche Zahl, die nur durch sich selbst und durch 1 teilbar ist. Die Zahl 1 ist keine Primzahl.

Unter Primfaktorzerlegung versteht man, die Darstellung einer natürlichen Zahl als Produkt von Primzahlen. Die in der Primfaktorzerlegung einer Zahl auftretenden Primzahlen nennt man die Primfaktoren dieser Zahl. Aus Primzahlen setzen sich die anderen Zahlen zusammen.

[bearbeiten]

Hauptsatz der elementaren Zahlentheorie

Jedes m $\in \mathbb {N}$ mit m > 1 hat genau eine Primfaktorzerlegung

m = $p_1^k1 * p_2^k2 *....*p_r^kr$

wobei $p 1 < p 2 < ... < p r$ Primzahlen sind, $k_1,k_2,....,k_r \in \mathbb {N}$ und r $\in \mathbb {N}.$

[bearbeiten]

Die Modulo-Rechnung

Modulo oder abgekürzt "mod" ist eine insbesondere in der Informatik verbreitete Funktion, die den Rest aus der Division zweier Ganzzahlen angibt.

a $\equiv$ b (mod m) -> a mod m = b mod m ( ist kongruent b modulo m)

a $\not\equiv$ b (mod m) -> a mod m $\not=$ mod m

[bearbeiten]

Berechnung der Eulerschen Phi-Funktion

Die eulersche Phi-Funktion ist nach Leonhard Euler benannt und wird mit dem grieschischen Buchstaben φ dargestellt. Die Phi-Funktion ist eine zahlentheoretische Funktion. Sie gibt für jede natürliche Zahl n an, wie viele natürliche Zahlen zwischen 1 und n zu ihr teilerfremd sind.


p Primzahl		$φ$ (p) = p -1,
p Primzahl und n $\equiv \mathbb {N}$		$φ(p n)$ = $p n - 1$ * (p-1)
x,y $\equiv \mathbb {N}$ mit ggT(x,y)		$φ$ (xy) = $φ(x) φ(y)$