Um längere Rechnungen zu vermeiden, rechnen wir:

(25001 - 95) mod 5 ≡ (25001 mod 5 - 95 mod 5) mod 5.

25001 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 25001 = 25000+1 = 5 ⋅ 5000 +1.

95 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 95 = 90+5 = 5 ⋅ 18 +5.

Somit gilt:

(25001 - 95) mod 5 ≡ (1 - 0) mod 5 ≡ 1 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(77 ⋅ 40) mod 8 ≡ (77 mod 8 ⋅ 40 mod 8) mod 8.

77 mod 8 ≡ 5 mod 8 kann man relativ leicht bestimmen, weil ja 77 = 72 + 5 = 9 ⋅ 8 + 5 ist.

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

Somit gilt:

(77 ⋅ 40) mod 8 ≡ (5 ⋅ 0) mod 8 ≡ 0 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: 202¹=202

2: 202²=202¹⁺¹=202¹⋅202¹ ≡ 202⋅202=40804 ≡ 147 mod 373

4: 202⁴=202²⁺²=202²⋅202² ≡ 147⋅147=21609 ≡ 348 mod 373

8: 202⁸=202⁴⁺⁴=202⁴⋅202⁴ ≡ 348⋅348=121104 ≡ 252 mod 373

16: 202¹⁶=202⁸⁺⁸=202⁸⋅202⁸ ≡ 252⋅252=63504 ≡ 94 mod 373

32: 202³²=202¹⁶⁺¹⁶=202¹⁶⋅202¹⁶ ≡ 94⋅94=8836 ≡ 257 mod 373

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

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

237 = 128+64+32+8+4+1

647²³⁷

= 647^{128+64+32+8+4+1}

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

≡ 440 ⋅ 456 ⋅ 387 ⋅ 569 ⋅ 627 ⋅ 647 mod 701
≡ 200640 ⋅ 387 ⋅ 569 ⋅ 627 ⋅ 647 mod 701 ≡ 154 ⋅ 387 ⋅ 569 ⋅ 627 ⋅ 647 mod 701
≡ 59598 ⋅ 569 ⋅ 627 ⋅ 647 mod 701 ≡ 13 ⋅ 569 ⋅ 627 ⋅ 647 mod 701
≡ 7397 ⋅ 627 ⋅ 647 mod 701 ≡ 387 ⋅ 627 ⋅ 647 mod 701
≡ 242649 ⋅ 647 mod 701 ≡ 103 ⋅ 647 mod 701
≡ 66641 mod 701 ≡ 46 mod 701

Es gilt also: 647²³⁷ ≡ 46 mod 701

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

=>83	= 1⋅68 + 15
=>68	= 4⋅15 + 8
=>15	= 1⋅8 + 7
=>8	= 1⋅7 + 1
=>7	= 7⋅1 + 0

also gilt: ggt(83,68)=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= 8-1⋅7
7= 15-1⋅8	eingesetzt in die Zeile drüber:	1	= 1⋅8 -1⋅(15 -1⋅ 8) = 1⋅8 -1⋅15 +1⋅ 8) = -1⋅15 +2⋅ 8 (=1)
8= 68-4⋅15	eingesetzt in die Zeile drüber:	1	= -1⋅15 +2⋅(68 -4⋅ 15) = -1⋅15 +2⋅68 -8⋅ 15) = 2⋅68 -9⋅ 15 (=1)
15= 83-1⋅68	eingesetzt in die Zeile drüber:	1	= 2⋅68 -9⋅(83 -1⋅ 68) = 2⋅68 -9⋅83 +9⋅ 68) = -9⋅83 +11⋅ 68 (=1)

Es gilt also: ggt(83,68)=1 = -9⋅83 +11⋅68

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

1 +9⋅83 = +11⋅68

Es gilt also: 11⋅68 = 9⋅83 +1

Somit 11⋅68 = 1 mod 83

11 ist also das Inverse von 68 mod 83