Um längere Rechnungen zu vermeiden, rechnen wir:

(117 + 1500) mod 3 ≡ (117 mod 3 + 1500 mod 3) mod 3.

117 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 117 = 120-3 = 3 ⋅ 40 -3 = 3 ⋅ 40 - 3 + 0.

1500 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 1500 = 1500+0 = 3 ⋅ 500 +0.

Somit gilt:

(117 + 1500) mod 3 ≡ (0 + 0) mod 3 ≡ 0 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(41 ⋅ 63) mod 7 ≡ (41 mod 7 ⋅ 63 mod 7) mod 7.

41 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 41 = 35 + 6 = 5 ⋅ 7 + 6 ist.

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

Somit gilt:

(41 ⋅ 63) mod 7 ≡ (6 ⋅ 0) mod 7 ≡ 0 mod 7.

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

2: 319²=319¹⁺¹=319¹⋅319¹ ≡ 319⋅319=101761 ≡ 546 mod 653

4: 319⁴=319²⁺²=319²⋅319² ≡ 546⋅546=298116 ≡ 348 mod 653

8: 319⁸=319⁴⁺⁴=319⁴⋅319⁴ ≡ 348⋅348=121104 ≡ 299 mod 653

16: 319¹⁶=319⁸⁺⁸=319⁸⋅319⁸ ≡ 299⋅299=89401 ≡ 593 mod 653

32: 319³²=319¹⁶⁺¹⁶=319¹⁶⋅319¹⁶ ≡ 593⋅593=351649 ≡ 335 mod 653

64: 319⁶⁴=319³²⁺³²=319³²⋅319³² ≡ 335⋅335=112225 ≡ 562 mod 653

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

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

215 = 128+64+16+4+2+1

72²¹⁵

= 72^{128+64+16+4+2+1}

= 72¹²⁸⋅72⁶⁴⋅72¹⁶⋅72⁴⋅72²⋅72¹

≡ 220 ⋅ 144 ⋅ 65 ⋅ 126 ⋅ 55 ⋅ 72 mod 223
≡ 31680 ⋅ 65 ⋅ 126 ⋅ 55 ⋅ 72 mod 223 ≡ 14 ⋅ 65 ⋅ 126 ⋅ 55 ⋅ 72 mod 223
≡ 910 ⋅ 126 ⋅ 55 ⋅ 72 mod 223 ≡ 18 ⋅ 126 ⋅ 55 ⋅ 72 mod 223
≡ 2268 ⋅ 55 ⋅ 72 mod 223 ≡ 38 ⋅ 55 ⋅ 72 mod 223
≡ 2090 ⋅ 72 mod 223 ≡ 83 ⋅ 72 mod 223
≡ 5976 mod 223 ≡ 178 mod 223

Es gilt also: 72²¹⁵ ≡ 178 mod 223

Berechnung des größten gemeinsamen Teilers von 61 und 19

=>61	= 3⋅19 + 4
=>19	= 4⋅4 + 3
=>4	= 1⋅3 + 1
=>3	= 3⋅1 + 0

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

Es gilt also: ggt(61,19)=1 = 5⋅61 -16⋅19

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

1 -5⋅61 = -16⋅19

-16⋅19 = -5⋅61 + 1 |+61⋅19

-16⋅19 + 61⋅19 = -5⋅61 + 61⋅19 + 1

(-16 + 61) ⋅ 19 = (-5 + 19) ⋅ 61 + 1

45⋅19 = 14⋅61 + 1

Es gilt also: 45⋅19 = 14⋅61 +1

Somit 45⋅19 = 1 mod 61

45 ist also das Inverse von 19 mod 61