Um längere Rechnungen zu vermeiden, rechnen wir:

(503 - 1504) mod 5 ≡ (503 mod 5 - 1504 mod 5) mod 5.

503 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 503 = 500+3 = 5 ⋅ 100 +3.

1504 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 1504 = 1500+4 = 5 ⋅ 300 +4.

Somit gilt:

(503 - 1504) mod 5 ≡ (3 - 4) mod 5 ≡ -1 mod 5 ≡ 4 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(69 ⋅ 46) mod 4 ≡ (69 mod 4 ⋅ 46 mod 4) mod 4.

69 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 69 = 68 + 1 = 17 ⋅ 4 + 1 ist.

46 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 46 = 44 + 2 = 11 ⋅ 4 + 2 ist.

Somit gilt:

(69 ⋅ 46) mod 4 ≡ (1 ⋅ 2) mod 4 ≡ 2 mod 4.

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

2: 146²=146¹⁺¹=146¹⋅146¹ ≡ 146⋅146=21316 ≡ 133 mod 307

4: 146⁴=146²⁺²=146²⋅146² ≡ 133⋅133=17689 ≡ 190 mod 307

8: 146⁸=146⁴⁺⁴=146⁴⋅146⁴ ≡ 190⋅190=36100 ≡ 181 mod 307

16: 146¹⁶=146⁸⁺⁸=146⁸⋅146⁸ ≡ 181⋅181=32761 ≡ 219 mod 307

32: 146³²=146¹⁶⁺¹⁶=146¹⁶⋅146¹⁶ ≡ 219⋅219=47961 ≡ 69 mod 307

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

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

185 = 128+32+16+8+1

442¹⁸⁵

= 442^{128+32+16+8+1}

= 442¹²⁸⋅442³²⋅442¹⁶⋅442⁸⋅442¹

≡ 287 ⋅ 129 ⋅ 230 ⋅ 70 ⋅ 442 mod 467
≡ 37023 ⋅ 230 ⋅ 70 ⋅ 442 mod 467 ≡ 130 ⋅ 230 ⋅ 70 ⋅ 442 mod 467
≡ 29900 ⋅ 70 ⋅ 442 mod 467 ≡ 12 ⋅ 70 ⋅ 442 mod 467
≡ 840 ⋅ 442 mod 467 ≡ 373 ⋅ 442 mod 467
≡ 164866 mod 467 ≡ 15 mod 467

Es gilt also: 442¹⁸⁵ ≡ 15 mod 467

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

=>61	= 2⋅26 + 9
=>26	= 2⋅9 + 8
=>9	= 1⋅8 + 1
=>8	= 8⋅1 + 0

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

Es gilt also: ggt(61,26)=1 = 3⋅61 -7⋅26

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

1 -3⋅61 = -7⋅26

-7⋅26 = -3⋅61 + 1 |+61⋅26

-7⋅26 + 61⋅26 = -3⋅61 + 61⋅26 + 1

(-7 + 61) ⋅ 26 = (-3 + 26) ⋅ 61 + 1

54⋅26 = 23⋅61 + 1

Es gilt also: 54⋅26 = 23⋅61 +1

Somit 54⋅26 = 1 mod 61

54 ist also das Inverse von 26 mod 61