Um längere Rechnungen zu vermeiden, rechnen wir:

(102 - 15004) mod 5 ≡ (102 mod 5 - 15004 mod 5) mod 5.

102 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 102 = 100+2 = 5 ⋅ 20 +2.

15004 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 15004 = 15000+4 = 5 ⋅ 3000 +4.

Somit gilt:

(102 - 15004) mod 5 ≡ (2 - 4) mod 5 ≡ -2 mod 5 ≡ 3 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(72 ⋅ 91) mod 10 ≡ (72 mod 10 ⋅ 91 mod 10) mod 10.

72 mod 10 ≡ 2 mod 10 kann man relativ leicht bestimmen, weil ja 72 = 70 + 2 = 7 ⋅ 10 + 2 ist.

91 mod 10 ≡ 1 mod 10 kann man relativ leicht bestimmen, weil ja 91 = 90 + 1 = 9 ⋅ 10 + 1 ist.

Somit gilt:

(72 ⋅ 91) mod 10 ≡ (2 ⋅ 1) mod 10 ≡ 2 mod 10.

Die 64 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: 351¹=351

2: 351²=351¹⁺¹=351¹⋅351¹ ≡ 351⋅351=123201 ≡ 281 mod 439

4: 351⁴=351²⁺²=351²⋅351² ≡ 281⋅281=78961 ≡ 380 mod 439

8: 351⁸=351⁴⁺⁴=351⁴⋅351⁴ ≡ 380⋅380=144400 ≡ 408 mod 439

16: 351¹⁶=351⁸⁺⁸=351⁸⋅351⁸ ≡ 408⋅408=166464 ≡ 83 mod 439

32: 351³²=351¹⁶⁺¹⁶=351¹⁶⋅351¹⁶ ≡ 83⋅83=6889 ≡ 304 mod 439

64: 351⁶⁴=351³²⁺³²=351³²⋅351³² ≡ 304⋅304=92416 ≡ 226 mod 439

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

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

87 = 64+16+4+2+1

318⁸⁷

= 318^64+16+4+2+1

= 318⁶⁴⋅318¹⁶⋅318⁴⋅318²⋅318¹

≡ 36 ⋅ 208 ⋅ 441 ⋅ 21 ⋅ 318 mod 503
≡ 7488 ⋅ 441 ⋅ 21 ⋅ 318 mod 503 ≡ 446 ⋅ 441 ⋅ 21 ⋅ 318 mod 503
≡ 196686 ⋅ 21 ⋅ 318 mod 503 ≡ 13 ⋅ 21 ⋅ 318 mod 503
≡ 273 ⋅ 318 mod 503
≡ 86814 mod 503 ≡ 298 mod 503

Es gilt also: 318⁸⁷ ≡ 298 mod 503

Berechnung des größten gemeinsamen Teilers von 101 und 72

=>101	= 1⋅72 + 29
=>72	= 2⋅29 + 14
=>29	= 2⋅14 + 1
=>14	= 14⋅1 + 0

also gilt: ggt(101,72)=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= 29-2⋅14
14= 72-2⋅29	eingesetzt in die Zeile drüber:	1	= 1⋅29 -2⋅(72 -2⋅ 29) = 1⋅29 -2⋅72 +4⋅ 29) = -2⋅72 +5⋅ 29 (=1)
29= 101-1⋅72	eingesetzt in die Zeile drüber:	1	= -2⋅72 +5⋅(101 -1⋅ 72) = -2⋅72 +5⋅101 -5⋅ 72) = 5⋅101 -7⋅ 72 (=1)

Es gilt also: ggt(101,72)=1 = 5⋅101 -7⋅72

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

1 -5⋅101 = -7⋅72

-7⋅72 = -5⋅101 + 1 |+101⋅72

-7⋅72 + 101⋅72 = -5⋅101 + 101⋅72 + 1

(-7 + 101) ⋅ 72 = (-5 + 72) ⋅ 101 + 1

94⋅72 = 67⋅101 + 1

Es gilt also: 94⋅72 = 67⋅101 +1

Somit 94⋅72 = 1 mod 101

94 ist also das Inverse von 72 mod 101