Um längere Rechnungen zu vermeiden, rechnen wir:

(92 + 597) mod 3 ≡ (92 mod 3 + 597 mod 3) mod 3.

92 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 92 = 90+2 = 3 ⋅ 30 +2.

597 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 597 = 600-3 = 3 ⋅ 200 -3 = 3 ⋅ 200 - 3 + 0.

Somit gilt:

(92 + 597) mod 3 ≡ (2 + 0) mod 3 ≡ 2 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

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

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

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

Somit gilt:

(91 ⋅ 70) mod 10 ≡ (1 ⋅ 0) mod 10 ≡ 0 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: 140¹=140

2: 140²=140¹⁺¹=140¹⋅140¹ ≡ 140⋅140=19600 ≡ 263 mod 317

4: 140⁴=140²⁺²=140²⋅140² ≡ 263⋅263=69169 ≡ 63 mod 317

8: 140⁸=140⁴⁺⁴=140⁴⋅140⁴ ≡ 63⋅63=3969 ≡ 165 mod 317

16: 140¹⁶=140⁸⁺⁸=140⁸⋅140⁸ ≡ 165⋅165=27225 ≡ 280 mod 317

32: 140³²=140¹⁶⁺¹⁶=140¹⁶⋅140¹⁶ ≡ 280⋅280=78400 ≡ 101 mod 317

64: 140⁶⁴=140³²⁺³²=140³²⋅140³² ≡ 101⋅101=10201 ≡ 57 mod 317

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

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

111 = 64+32+8+4+2+1

378¹¹¹

= 378^{64+32+8+4+2+1}

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

≡ 139 ⋅ 271 ⋅ 74 ⋅ 397 ⋅ 138 ⋅ 378 mod 643
≡ 37669 ⋅ 74 ⋅ 397 ⋅ 138 ⋅ 378 mod 643 ≡ 375 ⋅ 74 ⋅ 397 ⋅ 138 ⋅ 378 mod 643
≡ 27750 ⋅ 397 ⋅ 138 ⋅ 378 mod 643 ≡ 101 ⋅ 397 ⋅ 138 ⋅ 378 mod 643
≡ 40097 ⋅ 138 ⋅ 378 mod 643 ≡ 231 ⋅ 138 ⋅ 378 mod 643
≡ 31878 ⋅ 378 mod 643 ≡ 371 ⋅ 378 mod 643
≡ 140238 mod 643 ≡ 64 mod 643

Es gilt also: 378¹¹¹ ≡ 64 mod 643

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

=>61	= 3⋅18 + 7
=>18	= 2⋅7 + 4
=>7	= 1⋅4 + 3
=>4	= 1⋅3 + 1
=>3	= 3⋅1 + 0

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

Es gilt also: ggt(61,18)=1 = -5⋅61 +17⋅18

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

1 +5⋅61 = +17⋅18

Es gilt also: 17⋅18 = 5⋅61 +1

Somit 17⋅18 = 1 mod 61

17 ist also das Inverse von 18 mod 61