Um längere Rechnungen zu vermeiden, rechnen wir:

(2098 + 74) mod 7 ≡ (2098 mod 7 + 74 mod 7) mod 7.

2098 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 2098 = 2100-2 = 7 ⋅ 300 -2 = 7 ⋅ 300 - 7 + 5.

74 mod 7 ≡ 4 mod 7 kann man relativ leicht bestimmen, weil ja 74 = 70+4 = 7 ⋅ 10 +4.

Somit gilt:

(2098 + 74) mod 7 ≡ (5 + 4) mod 7 ≡ 9 mod 7 ≡ 2 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(63 ⋅ 69) mod 5 ≡ (63 mod 5 ⋅ 69 mod 5) mod 5.

63 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 63 = 60 + 3 = 12 ⋅ 5 + 3 ist.

69 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 69 = 65 + 4 = 13 ⋅ 5 + 4 ist.

Somit gilt:

(63 ⋅ 69) mod 5 ≡ (3 ⋅ 4) mod 5 ≡ 12 mod 5 ≡ 2 mod 5.

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: 382¹=382

2: 382²=382¹⁺¹=382¹⋅382¹ ≡ 382⋅382=145924 ≡ 459 mod 619

4: 382⁴=382²⁺²=382²⋅382² ≡ 459⋅459=210681 ≡ 221 mod 619

8: 382⁸=382⁴⁺⁴=382⁴⋅382⁴ ≡ 221⋅221=48841 ≡ 559 mod 619

16: 382¹⁶=382⁸⁺⁸=382⁸⋅382⁸ ≡ 559⋅559=312481 ≡ 505 mod 619

32: 382³²=382¹⁶⁺¹⁶=382¹⁶⋅382¹⁶ ≡ 505⋅505=255025 ≡ 616 mod 619

64: 382⁶⁴=382³²⁺³²=382³²⋅382³² ≡ 616⋅616=379456 ≡ 9 mod 619

128: 382¹²⁸=382⁶⁴⁺⁶⁴=382⁶⁴⋅382⁶⁴ ≡ 9⋅9=81 ≡ 81 mod 619

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

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

217 = 128+64+16+8+1

436²¹⁷

= 436^{128+64+16+8+1}

= 436¹²⁸⋅436⁶⁴⋅436¹⁶⋅436⁸⋅436¹

≡ 353 ⋅ 381 ⋅ 86 ⋅ 310 ⋅ 436 mod 787
≡ 134493 ⋅ 86 ⋅ 310 ⋅ 436 mod 787 ≡ 703 ⋅ 86 ⋅ 310 ⋅ 436 mod 787
≡ 60458 ⋅ 310 ⋅ 436 mod 787 ≡ 646 ⋅ 310 ⋅ 436 mod 787
≡ 200260 ⋅ 436 mod 787 ≡ 362 ⋅ 436 mod 787
≡ 157832 mod 787 ≡ 432 mod 787

Es gilt also: 436²¹⁷ ≡ 432 mod 787

Berechnung des größten gemeinsamen Teilers von 71 und 42

=>71	= 1⋅42 + 29
=>42	= 1⋅29 + 13
=>29	= 2⋅13 + 3
=>13	= 4⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(71,42)=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= 13-4⋅3
3= 29-2⋅13	eingesetzt in die Zeile drüber:	1	= 1⋅13 -4⋅(29 -2⋅ 13) = 1⋅13 -4⋅29 +8⋅ 13) = -4⋅29 +9⋅ 13 (=1)
13= 42-1⋅29	eingesetzt in die Zeile drüber:	1	= -4⋅29 +9⋅(42 -1⋅ 29) = -4⋅29 +9⋅42 -9⋅ 29) = 9⋅42 -13⋅ 29 (=1)
29= 71-1⋅42	eingesetzt in die Zeile drüber:	1	= 9⋅42 -13⋅(71 -1⋅ 42) = 9⋅42 -13⋅71 +13⋅ 42) = -13⋅71 +22⋅ 42 (=1)

Es gilt also: ggt(71,42)=1 = -13⋅71 +22⋅42

oder wenn man -13⋅71 auf die linke Seite bringt:

1 +13⋅71 = +22⋅42

Es gilt also: 22⋅42 = 13⋅71 +1

Somit 22⋅42 = 1 mod 71

22 ist also das Inverse von 42 mod 71