Um längere Rechnungen zu vermeiden, rechnen wir:

(599 + 2994) mod 6 ≡ (599 mod 6 + 2994 mod 6) mod 6.

599 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 599 = 600-1 = 6 ⋅ 100 -1 = 6 ⋅ 100 - 6 + 5.

2994 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 2994 = 3000-6 = 6 ⋅ 500 -6 = 6 ⋅ 500 - 6 + 0.

Somit gilt:

(599 + 2994) mod 6 ≡ (5 + 0) mod 6 ≡ 5 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(89 ⋅ 32) mod 4 ≡ (89 mod 4 ⋅ 32 mod 4) mod 4.

89 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 89 = 88 + 1 = 22 ⋅ 4 + 1 ist.

32 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 32 = 32 + 0 = 8 ⋅ 4 + 0 ist.

Somit gilt:

(89 ⋅ 32) mod 4 ≡ (1 ⋅ 0) mod 4 ≡ 0 mod 4.

Die 128 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: 163¹=163

2: 163²=163¹⁺¹=163¹⋅163¹ ≡ 163⋅163=26569 ≡ 214 mod 251

4: 163⁴=163²⁺²=163²⋅163² ≡ 214⋅214=45796 ≡ 114 mod 251

8: 163⁸=163⁴⁺⁴=163⁴⋅163⁴ ≡ 114⋅114=12996 ≡ 195 mod 251

16: 163¹⁶=163⁸⁺⁸=163⁸⋅163⁸ ≡ 195⋅195=38025 ≡ 124 mod 251

32: 163³²=163¹⁶⁺¹⁶=163¹⁶⋅163¹⁶ ≡ 124⋅124=15376 ≡ 65 mod 251

64: 163⁶⁴=163³²⁺³²=163³²⋅163³² ≡ 65⋅65=4225 ≡ 209 mod 251

128: 163¹²⁸=163⁶⁴⁺⁶⁴=163⁶⁴⋅163⁶⁴ ≡ 209⋅209=43681 ≡ 7 mod 251

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

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

101 = 64+32+4+1

680¹⁰¹

= 680^64+32+4+1

= 680⁶⁴⋅680³²⋅680⁴⋅680¹

≡ 619 ⋅ 215 ⋅ 130 ⋅ 680 mod 691
≡ 133085 ⋅ 130 ⋅ 680 mod 691 ≡ 413 ⋅ 130 ⋅ 680 mod 691
≡ 53690 ⋅ 680 mod 691 ≡ 483 ⋅ 680 mod 691
≡ 328440 mod 691 ≡ 215 mod 691

Es gilt also: 680¹⁰¹ ≡ 215 mod 691

Berechnung des größten gemeinsamen Teilers von 83 und 54

=>83	= 1⋅54 + 29
=>54	= 1⋅29 + 25
=>29	= 1⋅25 + 4
=>25	= 6⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(83,54)=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= 25-6⋅4
4= 29-1⋅25	eingesetzt in die Zeile drüber:	1	= 1⋅25 -6⋅(29 -1⋅ 25) = 1⋅25 -6⋅29 +6⋅ 25) = -6⋅29 +7⋅ 25 (=1)
25= 54-1⋅29	eingesetzt in die Zeile drüber:	1	= -6⋅29 +7⋅(54 -1⋅ 29) = -6⋅29 +7⋅54 -7⋅ 29) = 7⋅54 -13⋅ 29 (=1)
29= 83-1⋅54	eingesetzt in die Zeile drüber:	1	= 7⋅54 -13⋅(83 -1⋅ 54) = 7⋅54 -13⋅83 +13⋅ 54) = -13⋅83 +20⋅ 54 (=1)

Es gilt also: ggt(83,54)=1 = -13⋅83 +20⋅54

oder wenn man -13⋅83 auf die linke Seite bringt:

1 +13⋅83 = +20⋅54

Es gilt also: 20⋅54 = 13⋅83 +1

Somit 20⋅54 = 1 mod 83

20 ist also das Inverse von 54 mod 83