Um längere Rechnungen zu vermeiden, rechnen wir:

(297 - 11997) mod 3 ≡ (297 mod 3 - 11997 mod 3) mod 3.

297 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 297 = 300-3 = 3 ⋅ 100 -3 = 3 ⋅ 100 - 3 + 0.

11997 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 11997 = 12000-3 = 3 ⋅ 4000 -3 = 3 ⋅ 4000 - 3 + 0.

Somit gilt:

(297 - 11997) mod 3 ≡ (0 - 0) mod 3 ≡ 0 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(25 ⋅ 71) mod 8 ≡ (25 mod 8 ⋅ 71 mod 8) mod 8.

25 mod 8 ≡ 1 mod 8 kann man relativ leicht bestimmen, weil ja 25 = 24 + 1 = 3 ⋅ 8 + 1 ist.

71 mod 8 ≡ 7 mod 8 kann man relativ leicht bestimmen, weil ja 71 = 64 + 7 = 8 ⋅ 8 + 7 ist.

Somit gilt:

(25 ⋅ 71) mod 8 ≡ (1 ⋅ 7) mod 8 ≡ 7 mod 8.

Die 32 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: 116¹=116

2: 116²=116¹⁺¹=116¹⋅116¹ ≡ 116⋅116=13456 ≡ 201 mod 241

4: 116⁴=116²⁺²=116²⋅116² ≡ 201⋅201=40401 ≡ 154 mod 241

8: 116⁸=116⁴⁺⁴=116⁴⋅116⁴ ≡ 154⋅154=23716 ≡ 98 mod 241

16: 116¹⁶=116⁸⁺⁸=116⁸⋅116⁸ ≡ 98⋅98=9604 ≡ 205 mod 241

32: 116³²=116¹⁶⁺¹⁶=116¹⁶⋅116¹⁶ ≡ 205⋅205=42025 ≡ 91 mod 241

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

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

213 = 128+64+16+4+1

642²¹³

= 642^{128+64+16+4+1}

= 642¹²⁸⋅642⁶⁴⋅642¹⁶⋅642⁴⋅642¹

≡ 73 ⋅ 217 ⋅ 110 ⋅ 275 ⋅ 642 mod 653
≡ 15841 ⋅ 110 ⋅ 275 ⋅ 642 mod 653 ≡ 169 ⋅ 110 ⋅ 275 ⋅ 642 mod 653
≡ 18590 ⋅ 275 ⋅ 642 mod 653 ≡ 306 ⋅ 275 ⋅ 642 mod 653
≡ 84150 ⋅ 642 mod 653 ≡ 566 ⋅ 642 mod 653
≡ 363372 mod 653 ≡ 304 mod 653

Es gilt also: 642²¹³ ≡ 304 mod 653

Berechnung des größten gemeinsamen Teilers von 73 und 44

=>73	= 1⋅44 + 29
=>44	= 1⋅29 + 15
=>29	= 1⋅15 + 14
=>15	= 1⋅14 + 1
=>14	= 14⋅1 + 0

also gilt: ggt(73,44)=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= 15-1⋅14
14= 29-1⋅15	eingesetzt in die Zeile drüber:	1	= 1⋅15 -1⋅(29 -1⋅ 15) = 1⋅15 -1⋅29 +1⋅ 15) = -1⋅29 +2⋅ 15 (=1)
15= 44-1⋅29	eingesetzt in die Zeile drüber:	1	= -1⋅29 +2⋅(44 -1⋅ 29) = -1⋅29 +2⋅44 -2⋅ 29) = 2⋅44 -3⋅ 29 (=1)
29= 73-1⋅44	eingesetzt in die Zeile drüber:	1	= 2⋅44 -3⋅(73 -1⋅ 44) = 2⋅44 -3⋅73 +3⋅ 44) = -3⋅73 +5⋅ 44 (=1)

Es gilt also: ggt(73,44)=1 = -3⋅73 +5⋅44

oder wenn man -3⋅73 auf die linke Seite bringt:

1 +3⋅73 = +5⋅44

Es gilt also: 5⋅44 = 3⋅73 +1

Somit 5⋅44 = 1 mod 73

5 ist also das Inverse von 44 mod 73