Um längere Rechnungen zu vermeiden, rechnen wir:

(122 - 400) mod 4 ≡ (122 mod 4 - 400 mod 4) mod 4.

122 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 122 = 120+2 = 4 ⋅ 30 +2.

400 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 400 = 400+0 = 4 ⋅ 100 +0.

Somit gilt:

(122 - 400) mod 4 ≡ (2 - 0) mod 4 ≡ 2 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(19 ⋅ 43) mod 8 ≡ (19 mod 8 ⋅ 43 mod 8) mod 8.

19 mod 8 ≡ 3 mod 8 kann man relativ leicht bestimmen, weil ja 19 = 16 + 3 = 2 ⋅ 8 + 3 ist.

43 mod 8 ≡ 3 mod 8 kann man relativ leicht bestimmen, weil ja 43 = 40 + 3 = 5 ⋅ 8 + 3 ist.

Somit gilt:

(19 ⋅ 43) mod 8 ≡ (3 ⋅ 3) mod 8 ≡ 9 mod 8 ≡ 1 mod 8.

Die 8 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: 634¹=634

2: 634²=634¹⁺¹=634¹⋅634¹ ≡ 634⋅634=401956 ≡ 220 mod 881

4: 634⁴=634²⁺²=634²⋅634² ≡ 220⋅220=48400 ≡ 826 mod 881

8: 634⁸=634⁴⁺⁴=634⁴⋅634⁴ ≡ 826⋅826=682276 ≡ 382 mod 881

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

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

191 = 128+32+16+8+4+2+1

258¹⁹¹

= 258^{128+32+16+8+4+2+1}

= 258¹²⁸⋅258³²⋅258¹⁶⋅258⁸⋅258⁴⋅258²⋅258¹

≡ 151 ⋅ 211 ⋅ 242 ⋅ 135 ⋅ 52 ⋅ 137 ⋅ 258 mod 367
≡ 31861 ⋅ 242 ⋅ 135 ⋅ 52 ⋅ 137 ⋅ 258 mod 367 ≡ 299 ⋅ 242 ⋅ 135 ⋅ 52 ⋅ 137 ⋅ 258 mod 367
≡ 72358 ⋅ 135 ⋅ 52 ⋅ 137 ⋅ 258 mod 367 ≡ 59 ⋅ 135 ⋅ 52 ⋅ 137 ⋅ 258 mod 367
≡ 7965 ⋅ 52 ⋅ 137 ⋅ 258 mod 367 ≡ 258 ⋅ 52 ⋅ 137 ⋅ 258 mod 367
≡ 13416 ⋅ 137 ⋅ 258 mod 367 ≡ 204 ⋅ 137 ⋅ 258 mod 367
≡ 27948 ⋅ 258 mod 367 ≡ 56 ⋅ 258 mod 367
≡ 14448 mod 367 ≡ 135 mod 367

Es gilt also: 258¹⁹¹ ≡ 135 mod 367

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

=>59	= 1⋅44 + 15
=>44	= 2⋅15 + 14
=>15	= 1⋅14 + 1
=>14	= 14⋅1 + 0

also gilt: ggt(59,44)=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= 15-1⋅14
14= 44-2⋅15	eingesetzt in die Zeile drüber:	1	= 1⋅15 -1⋅(44 -2⋅ 15) = 1⋅15 -1⋅44 +2⋅ 15) = -1⋅44 +3⋅ 15 (=1)
15= 59-1⋅44	eingesetzt in die Zeile drüber:	1	= -1⋅44 +3⋅(59 -1⋅ 44) = -1⋅44 +3⋅59 -3⋅ 44) = 3⋅59 -4⋅ 44 (=1)

Es gilt also: ggt(59,44)=1 = 3⋅59 -4⋅44

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

1 -3⋅59 = -4⋅44

-4⋅44 = -3⋅59 + 1 |+59⋅44

-4⋅44 + 59⋅44 = -3⋅59 + 59⋅44 + 1

(-4 + 59) ⋅ 44 = (-3 + 44) ⋅ 59 + 1

55⋅44 = 41⋅59 + 1

Es gilt also: 55⋅44 = 41⋅59 +1

Somit 55⋅44 = 1 mod 59

55 ist also das Inverse von 44 mod 59