Um längere Rechnungen zu vermeiden, rechnen wir:

(102 + 499) mod 5 ≡ (102 mod 5 + 499 mod 5) mod 5.

102 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 102 = 100+2 = 5 ⋅ 20 +2.

499 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 499 = 400+99 = 5 ⋅ 80 +99.

Somit gilt:

(102 + 499) mod 5 ≡ (2 + 4) mod 5 ≡ 6 mod 5 ≡ 1 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(31 ⋅ 28) mod 4 ≡ (31 mod 4 ⋅ 28 mod 4) mod 4.

31 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 31 = 28 + 3 = 7 ⋅ 4 + 3 ist.

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

Somit gilt:

(31 ⋅ 28) mod 4 ≡ (3 ⋅ 0) mod 4 ≡ 0 mod 4.

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

2: 224²=224¹⁺¹=224¹⋅224¹ ≡ 224⋅224=50176 ≡ 158 mod 281

4: 224⁴=224²⁺²=224²⋅224² ≡ 158⋅158=24964 ≡ 236 mod 281

8: 224⁸=224⁴⁺⁴=224⁴⋅224⁴ ≡ 236⋅236=55696 ≡ 58 mod 281

16: 224¹⁶=224⁸⁺⁸=224⁸⋅224⁸ ≡ 58⋅58=3364 ≡ 273 mod 281

32: 224³²=224¹⁶⁺¹⁶=224¹⁶⋅224¹⁶ ≡ 273⋅273=74529 ≡ 64 mod 281

64: 224⁶⁴=224³²⁺³²=224³²⋅224³² ≡ 64⋅64=4096 ≡ 162 mod 281

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

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

233 = 128+64+32+8+1

411²³³

= 411^{128+64+32+8+1}

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

≡ 120 ⋅ 755 ⋅ 488 ⋅ 95 ⋅ 411 mod 857
≡ 90600 ⋅ 488 ⋅ 95 ⋅ 411 mod 857 ≡ 615 ⋅ 488 ⋅ 95 ⋅ 411 mod 857
≡ 300120 ⋅ 95 ⋅ 411 mod 857 ≡ 170 ⋅ 95 ⋅ 411 mod 857
≡ 16150 ⋅ 411 mod 857 ≡ 724 ⋅ 411 mod 857
≡ 297564 mod 857 ≡ 185 mod 857

Es gilt also: 411²³³ ≡ 185 mod 857

Berechnung des größten gemeinsamen Teilers von 101 und 67

=>101	= 1⋅67 + 34
=>67	= 1⋅34 + 33
=>34	= 1⋅33 + 1
=>33	= 33⋅1 + 0

also gilt: ggt(101,67)=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= 34-1⋅33
33= 67-1⋅34	eingesetzt in die Zeile drüber:	1	= 1⋅34 -1⋅(67 -1⋅ 34) = 1⋅34 -1⋅67 +1⋅ 34) = -1⋅67 +2⋅ 34 (=1)
34= 101-1⋅67	eingesetzt in die Zeile drüber:	1	= -1⋅67 +2⋅(101 -1⋅ 67) = -1⋅67 +2⋅101 -2⋅ 67) = 2⋅101 -3⋅ 67 (=1)

Es gilt also: ggt(101,67)=1 = 2⋅101 -3⋅67

oder wenn man 2⋅101 auf die linke Seite bringt:

1 -2⋅101 = -3⋅67

-3⋅67 = -2⋅101 + 1 |+101⋅67

-3⋅67 + 101⋅67 = -2⋅101 + 101⋅67 + 1

(-3 + 101) ⋅ 67 = (-2 + 67) ⋅ 101 + 1

98⋅67 = 65⋅101 + 1

Es gilt also: 98⋅67 = 65⋅101 +1

Somit 98⋅67 = 1 mod 101

98 ist also das Inverse von 67 mod 101