Um längere Rechnungen zu vermeiden, rechnen wir:

(172 + 2707) mod 9 ≡ (172 mod 9 + 2707 mod 9) mod 9.

172 mod 9 ≡ 1 mod 9 kann man relativ leicht bestimmen, weil ja 172 = 180-8 = 9 ⋅ 20 -8 = 9 ⋅ 20 - 9 + 1.

2707 mod 9 ≡ 7 mod 9 kann man relativ leicht bestimmen, weil ja 2707 = 2700+7 = 9 ⋅ 300 +7.

Somit gilt:

(172 + 2707) mod 9 ≡ (1 + 7) mod 9 ≡ 8 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(95 ⋅ 79) mod 6 ≡ (95 mod 6 ⋅ 79 mod 6) mod 6.

95 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 95 = 90 + 5 = 15 ⋅ 6 + 5 ist.

79 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 79 = 78 + 1 = 13 ⋅ 6 + 1 ist.

Somit gilt:

(95 ⋅ 79) mod 6 ≡ (5 ⋅ 1) mod 6 ≡ 5 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: 97¹=97

2: 97²=97¹⁺¹=97¹⋅97¹ ≡ 97⋅97=9409 ≡ 10 mod 241

4: 97⁴=97²⁺²=97²⋅97² ≡ 10⋅10=100 ≡ 100 mod 241

8: 97⁸=97⁴⁺⁴=97⁴⋅97⁴ ≡ 100⋅100=10000 ≡ 119 mod 241

16: 97¹⁶=97⁸⁺⁸=97⁸⋅97⁸ ≡ 119⋅119=14161 ≡ 183 mod 241

32: 97³²=97¹⁶⁺¹⁶=97¹⁶⋅97¹⁶ ≡ 183⋅183=33489 ≡ 231 mod 241

64: 97⁶⁴=97³²⁺³²=97³²⋅97³² ≡ 231⋅231=53361 ≡ 100 mod 241

128: 97¹²⁸=97⁶⁴⁺⁶⁴=97⁶⁴⋅97⁶⁴ ≡ 100⋅100=10000 ≡ 119 mod 241

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

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

141 = 128+8+4+1

491¹⁴¹

= 491^128+8+4+1

= 491¹²⁸⋅491⁸⋅491⁴⋅491¹

≡ 181 ⋅ 123 ⋅ 122 ⋅ 491 mod 509
≡ 22263 ⋅ 122 ⋅ 491 mod 509 ≡ 376 ⋅ 122 ⋅ 491 mod 509
≡ 45872 ⋅ 491 mod 509 ≡ 62 ⋅ 491 mod 509
≡ 30442 mod 509 ≡ 411 mod 509

Es gilt also: 491¹⁴¹ ≡ 411 mod 509

Berechnung des größten gemeinsamen Teilers von 59 und 54

=>59	= 1⋅54 + 5
=>54	= 10⋅5 + 4
=>5	= 1⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(59,54)=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= 5-1⋅4
4= 54-10⋅5	eingesetzt in die Zeile drüber:	1	= 1⋅5 -1⋅(54 -10⋅ 5) = 1⋅5 -1⋅54 +10⋅ 5) = -1⋅54 +11⋅ 5 (=1)
5= 59-1⋅54	eingesetzt in die Zeile drüber:	1	= -1⋅54 +11⋅(59 -1⋅ 54) = -1⋅54 +11⋅59 -11⋅ 54) = 11⋅59 -12⋅ 54 (=1)

Es gilt also: ggt(59,54)=1 = 11⋅59 -12⋅54

oder wenn man 11⋅59 auf die linke Seite bringt:

1 -11⋅59 = -12⋅54

-12⋅54 = -11⋅59 + 1 |+59⋅54

-12⋅54 + 59⋅54 = -11⋅59 + 59⋅54 + 1

(-12 + 59) ⋅ 54 = (-11 + 54) ⋅ 59 + 1

47⋅54 = 43⋅59 + 1

Es gilt also: 47⋅54 = 43⋅59 +1

Somit 47⋅54 = 1 mod 59

47 ist also das Inverse von 54 mod 59