Um längere Rechnungen zu vermeiden, rechnen wir:

(300 + 3006) mod 6 ≡ (300 mod 6 + 3006 mod 6) mod 6.

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

3006 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 3006 = 3000+6 = 6 ⋅ 500 +6.

Somit gilt:

(300 + 3006) mod 6 ≡ (0 + 0) mod 6 ≡ 0 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(26 ⋅ 84) mod 4 ≡ (26 mod 4 ⋅ 84 mod 4) mod 4.

26 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 26 = 24 + 2 = 6 ⋅ 4 + 2 ist.

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

Somit gilt:

(26 ⋅ 84) mod 4 ≡ (2 ⋅ 0) mod 4 ≡ 0 mod 4.

Die 128 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: 255¹=255

2: 255²=255¹⁺¹=255¹⋅255¹ ≡ 255⋅255=65025 ≡ 248 mod 307

4: 255⁴=255²⁺²=255²⋅255² ≡ 248⋅248=61504 ≡ 104 mod 307

8: 255⁸=255⁴⁺⁴=255⁴⋅255⁴ ≡ 104⋅104=10816 ≡ 71 mod 307

16: 255¹⁶=255⁸⁺⁸=255⁸⋅255⁸ ≡ 71⋅71=5041 ≡ 129 mod 307

32: 255³²=255¹⁶⁺¹⁶=255¹⁶⋅255¹⁶ ≡ 129⋅129=16641 ≡ 63 mod 307

64: 255⁶⁴=255³²⁺³²=255³²⋅255³² ≡ 63⋅63=3969 ≡ 285 mod 307

128: 255¹²⁸=255⁶⁴⁺⁶⁴=255⁶⁴⋅255⁶⁴ ≡ 285⋅285=81225 ≡ 177 mod 307

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

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

62 = 32+16+8+4+2

189⁶²

= 189^32+16+8+4+2

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

≡ 351 ⋅ 110 ⋅ 114 ⋅ 308 ⋅ 95 mod 379
≡ 38610 ⋅ 114 ⋅ 308 ⋅ 95 mod 379 ≡ 331 ⋅ 114 ⋅ 308 ⋅ 95 mod 379
≡ 37734 ⋅ 308 ⋅ 95 mod 379 ≡ 213 ⋅ 308 ⋅ 95 mod 379
≡ 65604 ⋅ 95 mod 379 ≡ 37 ⋅ 95 mod 379
≡ 3515 mod 379 ≡ 104 mod 379

Es gilt also: 189⁶² ≡ 104 mod 379

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