Um längere Rechnungen zu vermeiden, rechnen wir:

(3194 - 403) mod 8 ≡ (3194 mod 8 - 403 mod 8) mod 8.

3194 mod 8 ≡ 2 mod 8 kann man relativ leicht bestimmen, weil ja 3194 = 3200-6 = 8 ⋅ 400 -6 = 8 ⋅ 400 - 8 + 2.

403 mod 8 ≡ 3 mod 8 kann man relativ leicht bestimmen, weil ja 403 = 400+3 = 8 ⋅ 50 +3.

Somit gilt:

(3194 - 403) mod 8 ≡ (2 - 3) mod 8 ≡ -1 mod 8 ≡ 7 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(34 ⋅ 57) mod 10 ≡ (34 mod 10 ⋅ 57 mod 10) mod 10.

34 mod 10 ≡ 4 mod 10 kann man relativ leicht bestimmen, weil ja 34 = 30 + 4 = 3 ⋅ 10 + 4 ist.

57 mod 10 ≡ 7 mod 10 kann man relativ leicht bestimmen, weil ja 57 = 50 + 7 = 5 ⋅ 10 + 7 ist.

Somit gilt:

(34 ⋅ 57) mod 10 ≡ (4 ⋅ 7) mod 10 ≡ 28 mod 10 ≡ 8 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: 430¹=430

2: 430²=430¹⁺¹=430¹⋅430¹ ≡ 430⋅430=184900 ≡ 467 mod 571

4: 430⁴=430²⁺²=430²⋅430² ≡ 467⋅467=218089 ≡ 538 mod 571

8: 430⁸=430⁴⁺⁴=430⁴⋅430⁴ ≡ 538⋅538=289444 ≡ 518 mod 571

16: 430¹⁶=430⁸⁺⁸=430⁸⋅430⁸ ≡ 518⋅518=268324 ≡ 525 mod 571

32: 430³²=430¹⁶⁺¹⁶=430¹⁶⋅430¹⁶ ≡ 525⋅525=275625 ≡ 403 mod 571

64: 430⁶⁴=430³²⁺³²=430³²⋅430³² ≡ 403⋅403=162409 ≡ 245 mod 571

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

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

238 = 128+64+32+8+4+2

86²³⁸

= 86^{128+64+32+8+4+2}

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

≡ 166 ⋅ 70 ⋅ 99 ⋅ 258 ⋅ 235 ⋅ 32 mod 263
≡ 11620 ⋅ 99 ⋅ 258 ⋅ 235 ⋅ 32 mod 263 ≡ 48 ⋅ 99 ⋅ 258 ⋅ 235 ⋅ 32 mod 263
≡ 4752 ⋅ 258 ⋅ 235 ⋅ 32 mod 263 ≡ 18 ⋅ 258 ⋅ 235 ⋅ 32 mod 263
≡ 4644 ⋅ 235 ⋅ 32 mod 263 ≡ 173 ⋅ 235 ⋅ 32 mod 263
≡ 40655 ⋅ 32 mod 263 ≡ 153 ⋅ 32 mod 263
≡ 4896 mod 263 ≡ 162 mod 263

Es gilt also: 86²³⁸ ≡ 162 mod 263

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