Um längere Rechnungen zu vermeiden, rechnen wir:

(16002 - 245) mod 8 ≡ (16002 mod 8 - 245 mod 8) mod 8.

16002 mod 8 ≡ 2 mod 8 kann man relativ leicht bestimmen, weil ja 16002 = 16000+2 = 8 ⋅ 2000 +2.

245 mod 8 ≡ 5 mod 8 kann man relativ leicht bestimmen, weil ja 245 = 240+5 = 8 ⋅ 30 +5.

Somit gilt:

(16002 - 245) mod 8 ≡ (2 - 5) mod 8 ≡ -3 mod 8 ≡ 5 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(99 ⋅ 57) mod 11 ≡ (99 mod 11 ⋅ 57 mod 11) mod 11.

99 mod 11 ≡ 0 mod 11 kann man relativ leicht bestimmen, weil ja 99 = 99 + 0 = 9 ⋅ 11 + 0 ist.

57 mod 11 ≡ 2 mod 11 kann man relativ leicht bestimmen, weil ja 57 = 55 + 2 = 5 ⋅ 11 + 2 ist.

Somit gilt:

(99 ⋅ 57) mod 11 ≡ (0 ⋅ 2) mod 11 ≡ 0 mod 11.

Die 32 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: 78¹=78

2: 78²=78¹⁺¹=78¹⋅78¹ ≡ 78⋅78=6084 ≡ 176 mod 211

4: 78⁴=78²⁺²=78²⋅78² ≡ 176⋅176=30976 ≡ 170 mod 211

8: 78⁸=78⁴⁺⁴=78⁴⋅78⁴ ≡ 170⋅170=28900 ≡ 204 mod 211

16: 78¹⁶=78⁸⁺⁸=78⁸⋅78⁸ ≡ 204⋅204=41616 ≡ 49 mod 211

32: 78³²=78¹⁶⁺¹⁶=78¹⁶⋅78¹⁶ ≡ 49⋅49=2401 ≡ 80 mod 211

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

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

123 = 64+32+16+8+2+1

560¹²³

= 560^{64+32+16+8+2+1}

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

≡ 505 ⋅ 213 ⋅ 407 ⋅ 557 ⋅ 253 ⋅ 560 mod 701
≡ 107565 ⋅ 407 ⋅ 557 ⋅ 253 ⋅ 560 mod 701 ≡ 312 ⋅ 407 ⋅ 557 ⋅ 253 ⋅ 560 mod 701
≡ 126984 ⋅ 557 ⋅ 253 ⋅ 560 mod 701 ≡ 103 ⋅ 557 ⋅ 253 ⋅ 560 mod 701
≡ 57371 ⋅ 253 ⋅ 560 mod 701 ≡ 590 ⋅ 253 ⋅ 560 mod 701
≡ 149270 ⋅ 560 mod 701 ≡ 658 ⋅ 560 mod 701
≡ 368480 mod 701 ≡ 455 mod 701

Es gilt also: 560¹²³ ≡ 455 mod 701

Berechnung des größten gemeinsamen Teilers von 79 und 41

=>79	= 1⋅41 + 38
=>41	= 1⋅38 + 3
=>38	= 12⋅3 + 2
=>3	= 1⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(79,41)=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= 3-1⋅2
2= 38-12⋅3	eingesetzt in die Zeile drüber:	1	= 1⋅3 -1⋅(38 -12⋅ 3) = 1⋅3 -1⋅38 +12⋅ 3) = -1⋅38 +13⋅ 3 (=1)
3= 41-1⋅38	eingesetzt in die Zeile drüber:	1	= -1⋅38 +13⋅(41 -1⋅ 38) = -1⋅38 +13⋅41 -13⋅ 38) = 13⋅41 -14⋅ 38 (=1)
38= 79-1⋅41	eingesetzt in die Zeile drüber:	1	= 13⋅41 -14⋅(79 -1⋅ 41) = 13⋅41 -14⋅79 +14⋅ 41) = -14⋅79 +27⋅ 41 (=1)

Es gilt also: ggt(79,41)=1 = -14⋅79 +27⋅41

oder wenn man -14⋅79 auf die linke Seite bringt:

1 +14⋅79 = +27⋅41

Es gilt also: 27⋅41 = 14⋅79 +1

Somit 27⋅41 = 1 mod 79

27 ist also das Inverse von 41 mod 79