Kapitel 3: Elementare Zahlentheorie Flashcards
Was ist eine Relation?
Eine Relation R auf einer Menge A ist eine Teilmenge der geordneten Paare aus AxA
Wann ist eine Relation refelxiv?
Wenn alle Elemente a aus A zu sich selber zeigen
Wann ist eine Relation symmertrisch?
Wenn alle alle Pfeile/Beziehungen zwischen Elementen in beide Richtungen zeigen
Wann ist eine Relation antisymmetrisch?
Wenn alle Pfeile/Beziehungen zwischen Elementen immer nur in eine Richtung zeigen
Was gilt, wenn bei einer antisymmetrischen Relation, doch eine symmetrie zwischen einem Element a und b besteht?
Dann sind a und b gleich, es gilt a=b
Wann ist eine Relation transitiv?
Falls es eine Beziehung von einem Element a zu einem Element c gibt, welches eine Beziehung zu einem dritten Element b besitzt, dann existiert auch eine Beziehung des ersten Elements a zum dritten Element b
Wann ist eine Relation eine Teilordnung (Halbordnung, Ordnung, partielle Ordnung)?
Wenn die Relation
* reflexiv
* antisymmetrisch und
* transitiv ist
Wann ist eine Relation eine Äquivalenzrelation?
Wenn die Relation
* reflexiv
* symmetrisch und
* transitiv ist
Wie sind Partitionen von Äquivalenzrelationen definiert?
Wie kann man die Tranitivität einer Äquivalenzrelation beweisen?
Wie Restklassen modulo m gibt es?
m viele
Wie ist eine lineare Ordnung definiert?
Was gilt für m selber, wenn gilt: Sei m eine ganze Zahl. Und m^2 ist gerade.
m selber ist auch gerade
Wann sind zwei Mengen gleichmächtig?
Wenn es eine bijektive Abbildung zwischen ihnen gibt
Wann ist eine Menge M abzählbar
Wenn es eine bijektive Abbildung mit den Natürlichen Zahlen als Urbildmenge gibt, oder wenn M endlich ist
Wie heißt eine Menge die nicht abzählbar ist?
überabzählbar
Wie ist eine Partition definiert?
Wie definiert sich eine Äquivalenzrelation für eine Partition von der Menge A
Wie viele Partitionen von A gibt es, die genau gleich zu einer bestimmten Äquivalenzrelation auf der Menge A sind?
Wie wird auf den natürlichen Zahlen eine Äquivalenzrelation definiert, sodass die ganzen Zahlen damit konstruiert werden?
Wie ist die Addition auf den ganzen Zahlen definiert?
Wie ist die Multiplikation auf den ganzen Zahlen definiert?
Wie ist die Operation kleiner gleich auf den ganzen Zahlen definiert?
Was bedeutet wohldefiniertheit?
Dass das ergebnis einer Operation nur von der Äquivalenzklassen und nicht von dessen Repräsentanten abhängt
Was bedeutet wohldefiniertheit?
Dass das ergebnis einer Operation nur von der Äquivalenzklassen und nicht von dessen Repräsentanten abhängt
Wie ist die Subtraktion auf den ganzen Zahlen definiert?
Wie wird auf der Menge NxZ eine Äquivalenzrelation für die rationalen Zahlen definiert?
Wie ist die Addition auf den ganzen Zahlen definiert?
Wie ist die Multiplikation auf den ganzen Zahlen definiert?
Wie ist die kleiner gleich Operation auf den ganzen Zahlen definiert?
Wie ist die Subtraktion auf den ganzen Zahlen definiert?
Wie ist die Division auf den ganzen Zahlen definiert?
Wie ist ein angeordneter Körper definiert?
Ist die Menge der rationalen Zahlen abzählbar?
Nein, sie ist überabzählbar
Wie lässt sich einfach ausgedrückt die überabzählbarkeit von den Reellen Zahlen beweisen?
Man bestimmt eine Folge aus Reellen Zahlen in dem Intervall (0,1), in dem alle Reellen Zahlen größer als null und kleiner als eins sein sollen. Man erkennt jedoch, dass man auf Basis der Zahlen in der Folge immer wieder neue Reelle Zahlen in dem Intervall erzeugen kann, und somit gibt es noch Zahlen, die doch noch nicht in der Folge vorkommen -> Widerspruch
Wie ist die Teilbarkeit definiert?
Welche Eigenschaften hat die Teilbarkeitsrelation über den Natürlichen Zahlen mit null?
- refelxiv
- antisymmetrisch
- transitiv
Welche Eigenschaften hat die Teilbarkeitsrelation über den ganzen Zahlen?
- reflexiv
- transitiv
Was folgt aus a teilt b1 und a teilt b2?
Wie ist eine Primzahl definiert?
Eine Zahl n ist eine Primzahl, wenn sie nur durch -n, n und -1, 1 teilbar ist
Wie viele Primzahlen gibt es?
Unendlich viele
Wie lässt sich die Primfaktorzerlegung formal aufschreiben?
Definiere den ggT
Definiere das kgV
Was gilt für ggt(x,y) mal kgV(x,y)?
ist gleich der Betrag von x mal y
Für kann man für x und y Elemente der Natürlichen Zahlen mit x größer-gleich y den ggT(x,y) noch schreiben?
ggT(x-y, y)
Definiere die Division mit Rest
Was ist äquivalent zu x ist kongruent zu y modulo m
m teilt x-y
Welche Eigenschaften hat die Kongruenz modulo Relation auf den ganzen Zahlen?
Äquivalenzrelation, also
* reflexiv
* symmetrisch
* transitiv
Wie sind Restklassen definiert?
Wie berechnet sich das additive inverse einer Restklasse?
Wann sind zwei Zahlen teilerfremd?
Wenn deren ggT=1 ist
Was besagt das Lemma von Euklid?