Um längere Rechnungen zu vermeiden, rechnen wir:

(246 + 1608) mod 8 ≡ (246 mod 8 + 1608 mod 8) mod 8.

246 mod 8 ≡ 6 mod 8 kann man relativ leicht bestimmen, weil ja 246 = 240+6 = 8 ⋅ 30 +6.

1608 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 1608 = 1600+8 = 8 ⋅ 200 +8.

Somit gilt:

(246 + 1608) mod 8 ≡ (6 + 0) mod 8 ≡ 6 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(97 ⋅ 43) mod 3 ≡ (97 mod 3 ⋅ 43 mod 3) mod 3.

97 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 97 = 96 + 1 = 32 ⋅ 3 + 1 ist.

43 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 43 = 42 + 1 = 14 ⋅ 3 + 1 ist.

Somit gilt:

(97 ⋅ 43) mod 3 ≡ (1 ⋅ 1) mod 3 ≡ 1 mod 3.

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

2: 717²=717¹⁺¹=717¹⋅717¹ ≡ 717⋅717=514089 ≡ 963 mod 983

4: 717⁴=717²⁺²=717²⋅717² ≡ 963⋅963=927369 ≡ 400 mod 983

8: 717⁸=717⁴⁺⁴=717⁴⋅717⁴ ≡ 400⋅400=160000 ≡ 754 mod 983

16: 717¹⁶=717⁸⁺⁸=717⁸⋅717⁸ ≡ 754⋅754=568516 ≡ 342 mod 983

32: 717³²=717¹⁶⁺¹⁶=717¹⁶⋅717¹⁶ ≡ 342⋅342=116964 ≡ 970 mod 983

64: 717⁶⁴=717³²⁺³²=717³²⋅717³² ≡ 970⋅970=940900 ≡ 169 mod 983

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

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

232 = 128+64+32+8

456²³²

= 456^128+64+32+8

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

≡ 642 ⋅ 51 ⋅ 590 ⋅ 574 mod 653
≡ 32742 ⋅ 590 ⋅ 574 mod 653 ≡ 92 ⋅ 590 ⋅ 574 mod 653
≡ 54280 ⋅ 574 mod 653 ≡ 81 ⋅ 574 mod 653
≡ 46494 mod 653 ≡ 131 mod 653

Es gilt also: 456²³² ≡ 131 mod 653

Berechnung des größten gemeinsamen Teilers von 89 und 36

=>89	= 2⋅36 + 17
=>36	= 2⋅17 + 2
=>17	= 8⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(89,36)=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= 17-8⋅2
2= 36-2⋅17	eingesetzt in die Zeile drüber:	1	= 1⋅17 -8⋅(36 -2⋅ 17) = 1⋅17 -8⋅36 +16⋅ 17) = -8⋅36 +17⋅ 17 (=1)
17= 89-2⋅36	eingesetzt in die Zeile drüber:	1	= -8⋅36 +17⋅(89 -2⋅ 36) = -8⋅36 +17⋅89 -34⋅ 36) = 17⋅89 -42⋅ 36 (=1)

Es gilt also: ggt(89,36)=1 = 17⋅89 -42⋅36

oder wenn man 17⋅89 auf die linke Seite bringt:

1 -17⋅89 = -42⋅36

-42⋅36 = -17⋅89 + 1 |+89⋅36

-42⋅36 + 89⋅36 = -17⋅89 + 89⋅36 + 1

(-42 + 89) ⋅ 36 = (-17 + 36) ⋅ 89 + 1

47⋅36 = 19⋅89 + 1

Es gilt also: 47⋅36 = 19⋅89 +1

Somit 47⋅36 = 1 mod 89

47 ist also das Inverse von 36 mod 89