Um längere Rechnungen zu vermeiden, rechnen wir:

(174 + 1802) mod 6 ≡ (174 mod 6 + 1802 mod 6) mod 6.

174 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 174 = 180-6 = 6 ⋅ 30 -6 = 6 ⋅ 30 - 6 + 0.

1802 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 1802 = 1800+2 = 6 ⋅ 300 +2.

Somit gilt:

(174 + 1802) mod 6 ≡ (0 + 2) mod 6 ≡ 2 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(36 ⋅ 99) mod 5 ≡ (36 mod 5 ⋅ 99 mod 5) mod 5.

36 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 36 = 35 + 1 = 7 ⋅ 5 + 1 ist.

99 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 99 = 95 + 4 = 19 ⋅ 5 + 4 ist.

Somit gilt:

(36 ⋅ 99) mod 5 ≡ (1 ⋅ 4) mod 5 ≡ 4 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: 94¹=94

2: 94²=94¹⁺¹=94¹⋅94¹ ≡ 94⋅94=8836 ≡ 128 mod 311

4: 94⁴=94²⁺²=94²⋅94² ≡ 128⋅128=16384 ≡ 212 mod 311

8: 94⁸=94⁴⁺⁴=94⁴⋅94⁴ ≡ 212⋅212=44944 ≡ 160 mod 311

16: 94¹⁶=94⁸⁺⁸=94⁸⋅94⁸ ≡ 160⋅160=25600 ≡ 98 mod 311

32: 94³²=94¹⁶⁺¹⁶=94¹⁶⋅94¹⁶ ≡ 98⋅98=9604 ≡ 274 mod 311

64: 94⁶⁴=94³²⁺³²=94³²⋅94³² ≡ 274⋅274=75076 ≡ 125 mod 311

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

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

103 = 64+32+4+2+1

404¹⁰³

= 404^64+32+4+2+1

= 404⁶⁴⋅404³²⋅404⁴⋅404²⋅404¹

≡ 517 ⋅ 333 ⋅ 14 ⋅ 350 ⋅ 404 mod 673
≡ 172161 ⋅ 14 ⋅ 350 ⋅ 404 mod 673 ≡ 546 ⋅ 14 ⋅ 350 ⋅ 404 mod 673
≡ 7644 ⋅ 350 ⋅ 404 mod 673 ≡ 241 ⋅ 350 ⋅ 404 mod 673
≡ 84350 ⋅ 404 mod 673 ≡ 225 ⋅ 404 mod 673
≡ 90900 mod 673 ≡ 45 mod 673

Es gilt also: 404¹⁰³ ≡ 45 mod 673

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