Um längere Rechnungen zu vermeiden, rechnen wir:

(26991 + 44994) mod 9 ≡ (26991 mod 9 + 44994 mod 9) mod 9.

26991 mod 9 ≡ 0 mod 9 kann man relativ leicht bestimmen, weil ja 26991 = 27000-9 = 9 ⋅ 3000 -9 = 9 ⋅ 3000 - 9 + 0.

44994 mod 9 ≡ 3 mod 9 kann man relativ leicht bestimmen, weil ja 44994 = 45000-6 = 9 ⋅ 5000 -6 = 9 ⋅ 5000 - 9 + 3.

Somit gilt:

(26991 + 44994) mod 9 ≡ (0 + 3) mod 9 ≡ 3 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(34 ⋅ 75) mod 6 ≡ (34 mod 6 ⋅ 75 mod 6) mod 6.

34 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 34 = 30 + 4 = 5 ⋅ 6 + 4 ist.

75 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 75 = 72 + 3 = 12 ⋅ 6 + 3 ist.

Somit gilt:

(34 ⋅ 75) mod 6 ≡ (4 ⋅ 3) mod 6 ≡ 12 mod 6 ≡ 0 mod 6.

Die 128 im Exponent ist ja ein reine 2er-Potenz (2⁷).

Deswegen quadrieren wir einfach mit jedem Schritt das Ergebnis und kommen so immer eine 2er-Potenz im Exponenten höher:

1: 164¹=164

2: 164²=164¹⁺¹=164¹⋅164¹ ≡ 164⋅164=26896 ≡ 390 mod 457

4: 164⁴=164²⁺²=164²⋅164² ≡ 390⋅390=152100 ≡ 376 mod 457

8: 164⁸=164⁴⁺⁴=164⁴⋅164⁴ ≡ 376⋅376=141376 ≡ 163 mod 457

16: 164¹⁶=164⁸⁺⁸=164⁸⋅164⁸ ≡ 163⋅163=26569 ≡ 63 mod 457

32: 164³²=164¹⁶⁺¹⁶=164¹⁶⋅164¹⁶ ≡ 63⋅63=3969 ≡ 313 mod 457

64: 164⁶⁴=164³²⁺³²=164³²⋅164³² ≡ 313⋅313=97969 ≡ 171 mod 457

128: 164¹²⁸=164⁶⁴⁺⁶⁴=164⁶⁴⋅164⁶⁴ ≡ 171⋅171=29241 ≡ 450 mod 457

Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 200 (grauer Kasten).

Dann schauen wir die Binärdarstellung von 200 an und zerlegen 200 in eine Summer von 2er-Potenzen:

200 = 128+64+8

231²⁰⁰

= 231^128+64+8

= 231¹²⁸⋅231⁶⁴⋅231⁸

≡ 374 ⋅ 168 ⋅ 33 mod 557
≡ 62832 ⋅ 33 mod 557 ≡ 448 ⋅ 33 mod 557
≡ 14784 mod 557 ≡ 302 mod 557

Es gilt also: 231²⁰⁰ ≡ 302 mod 557

Berechnung des größten gemeinsamen Teilers von 83 und 34

=>83	= 2⋅34 + 15
=>34	= 2⋅15 + 4
=>15	= 3⋅4 + 3
=>4	= 1⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(83,34)=1

Jetzt formen wir jede Zeile von unten nach oben um indem wir das Prokukt auf die andere Seite bringen.
Wir starten mit der zweitletzten Zeile:

1= 4-1⋅3
3= 15-3⋅4	eingesetzt in die Zeile drüber:	1	= 1⋅4 -1⋅(15 -3⋅ 4) = 1⋅4 -1⋅15 +3⋅ 4) = -1⋅15 +4⋅ 4 (=1)
4= 34-2⋅15	eingesetzt in die Zeile drüber:	1	= -1⋅15 +4⋅(34 -2⋅ 15) = -1⋅15 +4⋅34 -8⋅ 15) = 4⋅34 -9⋅ 15 (=1)
15= 83-2⋅34	eingesetzt in die Zeile drüber:	1	= 4⋅34 -9⋅(83 -2⋅ 34) = 4⋅34 -9⋅83 +18⋅ 34) = -9⋅83 +22⋅ 34 (=1)

Es gilt also: ggt(83,34)=1 = -9⋅83 +22⋅34

oder wenn man -9⋅83 auf die linke Seite bringt:

1 +9⋅83 = +22⋅34

Es gilt also: 22⋅34 = 9⋅83 +1

Somit 22⋅34 = 1 mod 83

22 ist also das Inverse von 34 mod 83