Um längere Rechnungen zu vermeiden, rechnen wir:

(12000 - 56) mod 6 ≡ (12000 mod 6 - 56 mod 6) mod 6.

12000 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 12000 = 12000+0 = 6 ⋅ 2000 +0.

56 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 56 = 60-4 = 6 ⋅ 10 -4 = 6 ⋅ 10 - 6 + 2.

Somit gilt:

(12000 - 56) mod 6 ≡ (0 - 2) mod 6 ≡ -2 mod 6 ≡ 4 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(81 ⋅ 50) mod 5 ≡ (81 mod 5 ⋅ 50 mod 5) mod 5.

81 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 81 = 80 + 1 = 16 ⋅ 5 + 1 ist.

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

Somit gilt:

(81 ⋅ 50) mod 5 ≡ (1 ⋅ 0) mod 5 ≡ 0 mod 5.

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

2: 655²=655¹⁺¹=655¹⋅655¹ ≡ 655⋅655=429025 ≡ 563 mod 757

4: 655⁴=655²⁺²=655²⋅655² ≡ 563⋅563=316969 ≡ 543 mod 757

8: 655⁸=655⁴⁺⁴=655⁴⋅655⁴ ≡ 543⋅543=294849 ≡ 376 mod 757

16: 655¹⁶=655⁸⁺⁸=655⁸⋅655⁸ ≡ 376⋅376=141376 ≡ 574 mod 757

32: 655³²=655¹⁶⁺¹⁶=655¹⁶⋅655¹⁶ ≡ 574⋅574=329476 ≡ 181 mod 757

64: 655⁶⁴=655³²⁺³²=655³²⋅655³² ≡ 181⋅181=32761 ≡ 210 mod 757

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

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

175 = 128+32+8+4+2+1

375¹⁷⁵

= 375^{128+32+8+4+2+1}

= 375¹²⁸⋅375³²⋅375⁸⋅375⁴⋅375²⋅375¹

≡ 372 ⋅ 318 ⋅ 29 ⋅ 237 ⋅ 275 ⋅ 375 mod 401
≡ 118296 ⋅ 29 ⋅ 237 ⋅ 275 ⋅ 375 mod 401 ≡ 1 ⋅ 29 ⋅ 237 ⋅ 275 ⋅ 375 mod 401
≡ 29 ⋅ 237 ⋅ 275 ⋅ 375 mod 401
≡ 6873 ⋅ 275 ⋅ 375 mod 401 ≡ 56 ⋅ 275 ⋅ 375 mod 401
≡ 15400 ⋅ 375 mod 401 ≡ 162 ⋅ 375 mod 401
≡ 60750 mod 401 ≡ 199 mod 401

Es gilt also: 375¹⁷⁵ ≡ 199 mod 401

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

=>73	= 2⋅33 + 7
=>33	= 4⋅7 + 5
=>7	= 1⋅5 + 2
=>5	= 2⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(73,33)=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= 5-2⋅2
2= 7-1⋅5	eingesetzt in die Zeile drüber:	1	= 1⋅5 -2⋅(7 -1⋅ 5) = 1⋅5 -2⋅7 +2⋅ 5) = -2⋅7 +3⋅ 5 (=1)
5= 33-4⋅7	eingesetzt in die Zeile drüber:	1	= -2⋅7 +3⋅(33 -4⋅ 7) = -2⋅7 +3⋅33 -12⋅ 7) = 3⋅33 -14⋅ 7 (=1)
7= 73-2⋅33	eingesetzt in die Zeile drüber:	1	= 3⋅33 -14⋅(73 -2⋅ 33) = 3⋅33 -14⋅73 +28⋅ 33) = -14⋅73 +31⋅ 33 (=1)

Es gilt also: ggt(73,33)=1 = -14⋅73 +31⋅33

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

1 +14⋅73 = +31⋅33

Es gilt also: 31⋅33 = 14⋅73 +1

Somit 31⋅33 = 1 mod 73

31 ist also das Inverse von 33 mod 73