Um längere Rechnungen zu vermeiden, rechnen wir:

(1997 - 198) mod 4 ≡ (1997 mod 4 - 198 mod 4) mod 4.

1997 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 1997 = 1900+97 = 4 ⋅ 475 +97.

198 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 198 = 200-2 = 4 ⋅ 50 -2 = 4 ⋅ 50 - 4 + 2.

Somit gilt:

(1997 - 198) mod 4 ≡ (1 - 2) mod 4 ≡ -1 mod 4 ≡ 3 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(45 ⋅ 96) mod 9 ≡ (45 mod 9 ⋅ 96 mod 9) mod 9.

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

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

Somit gilt:

(45 ⋅ 96) mod 9 ≡ (0 ⋅ 6) mod 9 ≡ 0 mod 9.

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

2: 253²=253¹⁺¹=253¹⋅253¹ ≡ 253⋅253=64009 ≡ 390 mod 563

4: 253⁴=253²⁺²=253²⋅253² ≡ 390⋅390=152100 ≡ 90 mod 563

8: 253⁸=253⁴⁺⁴=253⁴⋅253⁴ ≡ 90⋅90=8100 ≡ 218 mod 563

16: 253¹⁶=253⁸⁺⁸=253⁸⋅253⁸ ≡ 218⋅218=47524 ≡ 232 mod 563

32: 253³²=253¹⁶⁺¹⁶=253¹⁶⋅253¹⁶ ≡ 232⋅232=53824 ≡ 339 mod 563

64: 253⁶⁴=253³²⁺³²=253³²⋅253³² ≡ 339⋅339=114921 ≡ 69 mod 563

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

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

63 = 32+16+8+4+2+1

374⁶³

= 374^{32+16+8+4+2+1}

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

≡ 274 ⋅ 139 ⋅ 394 ⋅ 203 ⋅ 198 ⋅ 374 mod 907
≡ 38086 ⋅ 394 ⋅ 203 ⋅ 198 ⋅ 374 mod 907 ≡ 899 ⋅ 394 ⋅ 203 ⋅ 198 ⋅ 374 mod 907
≡ 354206 ⋅ 203 ⋅ 198 ⋅ 374 mod 907 ≡ 476 ⋅ 203 ⋅ 198 ⋅ 374 mod 907
≡ 96628 ⋅ 198 ⋅ 374 mod 907 ≡ 486 ⋅ 198 ⋅ 374 mod 907
≡ 96228 ⋅ 374 mod 907 ≡ 86 ⋅ 374 mod 907
≡ 32164 mod 907 ≡ 419 mod 907

Es gilt also: 374⁶³ ≡ 419 mod 907

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

=>61	= 2⋅27 + 7
=>27	= 3⋅7 + 6
=>7	= 1⋅6 + 1
=>6	= 6⋅1 + 0

also gilt: ggt(61,27)=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= 7-1⋅6
6= 27-3⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -1⋅(27 -3⋅ 7) = 1⋅7 -1⋅27 +3⋅ 7) = -1⋅27 +4⋅ 7 (=1)
7= 61-2⋅27	eingesetzt in die Zeile drüber:	1	= -1⋅27 +4⋅(61 -2⋅ 27) = -1⋅27 +4⋅61 -8⋅ 27) = 4⋅61 -9⋅ 27 (=1)

Es gilt also: ggt(61,27)=1 = 4⋅61 -9⋅27

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

1 -4⋅61 = -9⋅27

-9⋅27 = -4⋅61 + 1 |+61⋅27

-9⋅27 + 61⋅27 = -4⋅61 + 61⋅27 + 1

(-9 + 61) ⋅ 27 = (-4 + 27) ⋅ 61 + 1

52⋅27 = 23⋅61 + 1

Es gilt also: 52⋅27 = 23⋅61 +1

Somit 52⋅27 = 1 mod 61

52 ist also das Inverse von 27 mod 61