Um längere Rechnungen zu vermeiden, rechnen wir:

(5998 - 3006) mod 6 ≡ (5998 mod 6 - 3006 mod 6) mod 6.

5998 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 5998 = 6000-2 = 6 ⋅ 1000 -2 = 6 ⋅ 1000 - 6 + 4.

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

Somit gilt:

(5998 - 3006) mod 6 ≡ (4 - 0) mod 6 ≡ 4 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

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

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

61 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 61 = 60 + 1 = 15 ⋅ 4 + 1 ist.

Somit gilt:

(26 ⋅ 61) mod 4 ≡ (2 ⋅ 1) mod 4 ≡ 2 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: 314¹=314

2: 314²=314¹⁺¹=314¹⋅314¹ ≡ 314⋅314=98596 ≡ 230 mod 359

4: 314⁴=314²⁺²=314²⋅314² ≡ 230⋅230=52900 ≡ 127 mod 359

8: 314⁸=314⁴⁺⁴=314⁴⋅314⁴ ≡ 127⋅127=16129 ≡ 333 mod 359

16: 314¹⁶=314⁸⁺⁸=314⁸⋅314⁸ ≡ 333⋅333=110889 ≡ 317 mod 359

32: 314³²=314¹⁶⁺¹⁶=314¹⁶⋅314¹⁶ ≡ 317⋅317=100489 ≡ 328 mod 359

64: 314⁶⁴=314³²⁺³²=314³²⋅314³² ≡ 328⋅328=107584 ≡ 243 mod 359

128: 314¹²⁸=314⁶⁴⁺⁶⁴=314⁶⁴⋅314⁶⁴ ≡ 243⋅243=59049 ≡ 173 mod 359

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

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

116 = 64+32+16+4

226¹¹⁶

= 226^64+32+16+4

= 226⁶⁴⋅226³²⋅226¹⁶⋅226⁴

≡ 192 ⋅ 208 ⋅ 378 ⋅ 473 mod 673
≡ 39936 ⋅ 378 ⋅ 473 mod 673 ≡ 229 ⋅ 378 ⋅ 473 mod 673
≡ 86562 ⋅ 473 mod 673 ≡ 418 ⋅ 473 mod 673
≡ 197714 mod 673 ≡ 525 mod 673

Es gilt also: 226¹¹⁶ ≡ 525 mod 673

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

=>101	= 1⋅55 + 46
=>55	= 1⋅46 + 9
=>46	= 5⋅9 + 1
=>9	= 9⋅1 + 0

also gilt: ggt(101,55)=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= 46-5⋅9
9= 55-1⋅46	eingesetzt in die Zeile drüber:	1	= 1⋅46 -5⋅(55 -1⋅ 46) = 1⋅46 -5⋅55 +5⋅ 46) = -5⋅55 +6⋅ 46 (=1)
46= 101-1⋅55	eingesetzt in die Zeile drüber:	1	= -5⋅55 +6⋅(101 -1⋅ 55) = -5⋅55 +6⋅101 -6⋅ 55) = 6⋅101 -11⋅ 55 (=1)

Es gilt also: ggt(101,55)=1 = 6⋅101 -11⋅55

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

1 -6⋅101 = -11⋅55

-11⋅55 = -6⋅101 + 1 |+101⋅55

-11⋅55 + 101⋅55 = -6⋅101 + 101⋅55 + 1

(-11 + 101) ⋅ 55 = (-6 + 55) ⋅ 101 + 1

90⋅55 = 49⋅101 + 1

Es gilt also: 90⋅55 = 49⋅101 +1

Somit 90⋅55 = 1 mod 101

90 ist also das Inverse von 55 mod 101