Um längere Rechnungen zu vermeiden, rechnen wir:

(3997 - 3199) mod 8 ≡ (3997 mod 8 - 3199 mod 8) mod 8.

3997 mod 8 ≡ 5 mod 8 kann man relativ leicht bestimmen, weil ja 3997 = 4000-3 = 8 ⋅ 500 -3 = 8 ⋅ 500 - 8 + 5.

3199 mod 8 ≡ 7 mod 8 kann man relativ leicht bestimmen, weil ja 3199 = 3200-1 = 8 ⋅ 400 -1 = 8 ⋅ 400 - 8 + 7.

Somit gilt:

(3997 - 3199) mod 8 ≡ (5 - 7) mod 8 ≡ -2 mod 8 ≡ 6 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(54 ⋅ 75) mod 11 ≡ (54 mod 11 ⋅ 75 mod 11) mod 11.

54 mod 11 ≡ 10 mod 11 kann man relativ leicht bestimmen, weil ja 54 = 44 + 10 = 4 ⋅ 11 + 10 ist.

75 mod 11 ≡ 9 mod 11 kann man relativ leicht bestimmen, weil ja 75 = 66 + 9 = 6 ⋅ 11 + 9 ist.

Somit gilt:

(54 ⋅ 75) mod 11 ≡ (10 ⋅ 9) mod 11 ≡ 90 mod 11 ≡ 2 mod 11.

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 ≡ 662 mod 719

4: 508⁴=508²⁺²=508²⋅508² ≡ 662⋅662=438244 ≡ 373 mod 719

8: 508⁸=508⁴⁺⁴=508⁴⋅508⁴ ≡ 373⋅373=139129 ≡ 362 mod 719

16: 508¹⁶=508⁸⁺⁸=508⁸⋅508⁸ ≡ 362⋅362=131044 ≡ 186 mod 719

32: 508³²=508¹⁶⁺¹⁶=508¹⁶⋅508¹⁶ ≡ 186⋅186=34596 ≡ 84 mod 719

64: 508⁶⁴=508³²⁺³²=508³²⋅508³² ≡ 84⋅84=7056 ≡ 585 mod 719

128: 508¹²⁸=508⁶⁴⁺⁶⁴=508⁶⁴⋅508⁶⁴ ≡ 585⋅585=342225 ≡ 700 mod 719

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

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

127 = 64+32+16+8+4+2+1

291¹²⁷

= 291^{64+32+16+8+4+2+1}

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

≡ 441 ⋅ 21 ⋅ 408 ⋅ 199 ⋅ 357 ⋅ 187 ⋅ 291 mod 509
≡ 9261 ⋅ 408 ⋅ 199 ⋅ 357 ⋅ 187 ⋅ 291 mod 509 ≡ 99 ⋅ 408 ⋅ 199 ⋅ 357 ⋅ 187 ⋅ 291 mod 509
≡ 40392 ⋅ 199 ⋅ 357 ⋅ 187 ⋅ 291 mod 509 ≡ 181 ⋅ 199 ⋅ 357 ⋅ 187 ⋅ 291 mod 509
≡ 36019 ⋅ 357 ⋅ 187 ⋅ 291 mod 509 ≡ 389 ⋅ 357 ⋅ 187 ⋅ 291 mod 509
≡ 138873 ⋅ 187 ⋅ 291 mod 509 ≡ 425 ⋅ 187 ⋅ 291 mod 509
≡ 79475 ⋅ 291 mod 509 ≡ 71 ⋅ 291 mod 509
≡ 20661 mod 509 ≡ 301 mod 509

Es gilt also: 291¹²⁷ ≡ 301 mod 509

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

=>89	= 1⋅76 + 13
=>76	= 5⋅13 + 11
=>13	= 1⋅11 + 2
=>11	= 5⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(89,76)=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= 11-5⋅2
2= 13-1⋅11	eingesetzt in die Zeile drüber:	1	= 1⋅11 -5⋅(13 -1⋅ 11) = 1⋅11 -5⋅13 +5⋅ 11) = -5⋅13 +6⋅ 11 (=1)
11= 76-5⋅13	eingesetzt in die Zeile drüber:	1	= -5⋅13 +6⋅(76 -5⋅ 13) = -5⋅13 +6⋅76 -30⋅ 13) = 6⋅76 -35⋅ 13 (=1)
13= 89-1⋅76	eingesetzt in die Zeile drüber:	1	= 6⋅76 -35⋅(89 -1⋅ 76) = 6⋅76 -35⋅89 +35⋅ 76) = -35⋅89 +41⋅ 76 (=1)

Es gilt also: ggt(89,76)=1 = -35⋅89 +41⋅76

oder wenn man -35⋅89 auf die linke Seite bringt:

1 +35⋅89 = +41⋅76

Es gilt also: 41⋅76 = 35⋅89 +1

Somit 41⋅76 = 1 mod 89

41 ist also das Inverse von 76 mod 89