Um längere Rechnungen zu vermeiden, rechnen wir:

(2998 - 903) mod 3 ≡ (2998 mod 3 - 903 mod 3) mod 3.

2998 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 2998 = 3000-2 = 3 ⋅ 1000 -2 = 3 ⋅ 1000 - 3 + 1.

903 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 903 = 900+3 = 3 ⋅ 300 +3.

Somit gilt:

(2998 - 903) mod 3 ≡ (1 - 0) mod 3 ≡ 1 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(55 ⋅ 99) mod 6 ≡ (55 mod 6 ⋅ 99 mod 6) mod 6.

55 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 55 = 54 + 1 = 9 ⋅ 6 + 1 ist.

99 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 99 = 96 + 3 = 16 ⋅ 6 + 3 ist.

Somit gilt:

(55 ⋅ 99) mod 6 ≡ (1 ⋅ 3) mod 6 ≡ 3 mod 6.

Die 32 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: 91¹=91

2: 91²=91¹⁺¹=91¹⋅91¹ ≡ 91⋅91=8281 ≡ 109 mod 227

4: 91⁴=91²⁺²=91²⋅91² ≡ 109⋅109=11881 ≡ 77 mod 227

8: 91⁸=91⁴⁺⁴=91⁴⋅91⁴ ≡ 77⋅77=5929 ≡ 27 mod 227

16: 91¹⁶=91⁸⁺⁸=91⁸⋅91⁸ ≡ 27⋅27=729 ≡ 48 mod 227

32: 91³²=91¹⁶⁺¹⁶=91¹⁶⋅91¹⁶ ≡ 48⋅48=2304 ≡ 34 mod 227

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

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

239 = 128+64+32+8+4+2+1

159²³⁹

= 159^{128+64+32+8+4+2+1}

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

≡ 74 ⋅ 91 ⋅ 137 ⋅ 7 ⋅ 63 ⋅ 94 ⋅ 159 mod 283
≡ 6734 ⋅ 137 ⋅ 7 ⋅ 63 ⋅ 94 ⋅ 159 mod 283 ≡ 225 ⋅ 137 ⋅ 7 ⋅ 63 ⋅ 94 ⋅ 159 mod 283
≡ 30825 ⋅ 7 ⋅ 63 ⋅ 94 ⋅ 159 mod 283 ≡ 261 ⋅ 7 ⋅ 63 ⋅ 94 ⋅ 159 mod 283
≡ 1827 ⋅ 63 ⋅ 94 ⋅ 159 mod 283 ≡ 129 ⋅ 63 ⋅ 94 ⋅ 159 mod 283
≡ 8127 ⋅ 94 ⋅ 159 mod 283 ≡ 203 ⋅ 94 ⋅ 159 mod 283
≡ 19082 ⋅ 159 mod 283 ≡ 121 ⋅ 159 mod 283
≡ 19239 mod 283 ≡ 278 mod 283

Es gilt also: 159²³⁹ ≡ 278 mod 283

Berechnung des größten gemeinsamen Teilers von 89 und 52

=>89	= 1⋅52 + 37
=>52	= 1⋅37 + 15
=>37	= 2⋅15 + 7
=>15	= 2⋅7 + 1
=>7	= 7⋅1 + 0

also gilt: ggt(89,52)=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= 15-2⋅7
7= 37-2⋅15	eingesetzt in die Zeile drüber:	1	= 1⋅15 -2⋅(37 -2⋅ 15) = 1⋅15 -2⋅37 +4⋅ 15) = -2⋅37 +5⋅ 15 (=1)
15= 52-1⋅37	eingesetzt in die Zeile drüber:	1	= -2⋅37 +5⋅(52 -1⋅ 37) = -2⋅37 +5⋅52 -5⋅ 37) = 5⋅52 -7⋅ 37 (=1)
37= 89-1⋅52	eingesetzt in die Zeile drüber:	1	= 5⋅52 -7⋅(89 -1⋅ 52) = 5⋅52 -7⋅89 +7⋅ 52) = -7⋅89 +12⋅ 52 (=1)

Es gilt also: ggt(89,52)=1 = -7⋅89 +12⋅52

oder wenn man -7⋅89 auf die linke Seite bringt:

1 +7⋅89 = +12⋅52

Es gilt also: 12⋅52 = 7⋅89 +1

Somit 12⋅52 = 1 mod 89

12 ist also das Inverse von 52 mod 89