Um längere Rechnungen zu vermeiden, rechnen wir:

(796 - 159) mod 4 ≡ (796 mod 4 - 159 mod 4) mod 4.

796 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 796 = 700+96 = 4 ⋅ 175 +96.

159 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 159 = 160-1 = 4 ⋅ 40 -1 = 4 ⋅ 40 - 4 + 3.

Somit gilt:

(796 - 159) mod 4 ≡ (0 - 3) mod 4 ≡ -3 mod 4 ≡ 1 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(52 ⋅ 32) mod 6 ≡ (52 mod 6 ⋅ 32 mod 6) mod 6.

52 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 52 = 48 + 4 = 8 ⋅ 6 + 4 ist.

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

Somit gilt:

(52 ⋅ 32) mod 6 ≡ (4 ⋅ 2) mod 6 ≡ 8 mod 6 ≡ 2 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: 508¹=508

2: 508²=508¹⁺¹=508¹⋅508¹ ≡ 508⋅508=258064 ≡ 251 mod 911

4: 508⁴=508²⁺²=508²⋅508² ≡ 251⋅251=63001 ≡ 142 mod 911

8: 508⁸=508⁴⁺⁴=508⁴⋅508⁴ ≡ 142⋅142=20164 ≡ 122 mod 911

16: 508¹⁶=508⁸⁺⁸=508⁸⋅508⁸ ≡ 122⋅122=14884 ≡ 308 mod 911

32: 508³²=508¹⁶⁺¹⁶=508¹⁶⋅508¹⁶ ≡ 308⋅308=94864 ≡ 120 mod 911

64: 508⁶⁴=508³²⁺³²=508³²⋅508³² ≡ 120⋅120=14400 ≡ 735 mod 911

128: 508¹²⁸=508⁶⁴⁺⁶⁴=508⁶⁴⋅508⁶⁴ ≡ 735⋅735=540225 ≡ 2 mod 911

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

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

253 = 128+64+32+16+8+4+1

360²⁵³

= 360^{128+64+32+16+8+4+1}

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

≡ 169 ⋅ 13 ⋅ 348 ⋅ 102 ⋅ 334 ⋅ 300 ⋅ 360 mod 419
≡ 2197 ⋅ 348 ⋅ 102 ⋅ 334 ⋅ 300 ⋅ 360 mod 419 ≡ 102 ⋅ 348 ⋅ 102 ⋅ 334 ⋅ 300 ⋅ 360 mod 419
≡ 35496 ⋅ 102 ⋅ 334 ⋅ 300 ⋅ 360 mod 419 ≡ 300 ⋅ 102 ⋅ 334 ⋅ 300 ⋅ 360 mod 419
≡ 30600 ⋅ 334 ⋅ 300 ⋅ 360 mod 419 ≡ 13 ⋅ 334 ⋅ 300 ⋅ 360 mod 419
≡ 4342 ⋅ 300 ⋅ 360 mod 419 ≡ 152 ⋅ 300 ⋅ 360 mod 419
≡ 45600 ⋅ 360 mod 419 ≡ 348 ⋅ 360 mod 419
≡ 125280 mod 419 ≡ 418 mod 419

Es gilt also: 360²⁵³ ≡ 418 mod 419

Berechnung des größten gemeinsamen Teilers von 89 und 74

=>89	= 1⋅74 + 15
=>74	= 4⋅15 + 14
=>15	= 1⋅14 + 1
=>14	= 14⋅1 + 0

also gilt: ggt(89,74)=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= 74-4⋅15	eingesetzt in die Zeile drüber:	1	= 1⋅15 -1⋅(74 -4⋅ 15) = 1⋅15 -1⋅74 +4⋅ 15) = -1⋅74 +5⋅ 15 (=1)
15= 89-1⋅74	eingesetzt in die Zeile drüber:	1	= -1⋅74 +5⋅(89 -1⋅ 74) = -1⋅74 +5⋅89 -5⋅ 74) = 5⋅89 -6⋅ 74 (=1)

Es gilt also: ggt(89,74)=1 = 5⋅89 -6⋅74

oder wenn man 5⋅89 auf die linke Seite bringt:

1 -5⋅89 = -6⋅74

-6⋅74 = -5⋅89 + 1 |+89⋅74

-6⋅74 + 89⋅74 = -5⋅89 + 89⋅74 + 1

(-6 + 89) ⋅ 74 = (-5 + 74) ⋅ 89 + 1

83⋅74 = 69⋅89 + 1

Es gilt also: 83⋅74 = 69⋅89 +1

Somit 83⋅74 = 1 mod 89

83 ist also das Inverse von 74 mod 89