Mathematische Grundkenntnisse

Modulare Arithmetik

1 mod 2 = 1/2 = 0 Rest 1 => 1
2 mod 2 = 2/2 = 1 Rest 0 => 0
3 mod 2 = 3/2 = 1 Rest 1 => 1
4 mod 2 = 4/2 = 2 Rest 0 => 0

11 mod 6 = 11/6 = 1 Rest 5 => 5
12 mod 2 = 12/6 = 2 Rest 0 => 0
13 mod 2 = 13/6 = 2 Rest 1 => 1
14 mod 2 = 14/6 = 2 Rest 2 => 2

3^3 mod 7 = 27/7 = 3 Rest 6 => 6
3^4 mod 7 = 81/7 = 11 Rest 11 => 11
3^5 mod 7 = 243/7 = 34 Rest 5 => 5

Teilertheorie
Auffinden des größten gemeinsamen Teiler zweier Zahlen,
anhand des Euklidischen Algorithmus.

Beispiel 1: 21 und 128:
128 : 21 = 6 Rest 2
21 : 2 = 10 Rest 1
2 : 1 = 2 Rest 0

1 ist der größte gemeinsame Teiler von 21 und 128.
Daraus folgt nun, dass das kleinste gemeinsame Vielfache (128*21):1 = 2.688 ist.

Beispiel 2: 4 und 15:
15 : 4 = 3 Rest 3
4 : 3 = 1 Rest 1
3 : 1 = 3 Rest 0
1 ist der größte gemeinsame Teiler von 4 und 15.
Daraus folgt nun, dass das kleinste gemeinsame Vielfache (4*15):1 = 60 ist.

Beispiel 3: 429 und 595:
595 : 429 = 1 Rest 166
429 : 166 = 2 Rest 97
166: 97 = 1 Rest 69
97: 69 = 1 Rest 28
69 : 28 = 2 Rest 13
28 : 13 = 2 Rest 2
13 : 2 = 6 Rest 1
2 : 1 = 2 Rest 0
Auch hier ist 1 wieder der größte gemeinsame Teiler.