Um längere Rechnungen zu vermeiden, rechnen wir:

(17998 + 352) mod 9 ≡ (17998 mod 9 + 352 mod 9) mod 9.

17998 mod 9 ≡ 7 mod 9 kann man relativ leicht bestimmen, weil ja 17998 = 18000-2 = 9 ⋅ 2000 -2 = 9 ⋅ 2000 - 9 + 7.

352 mod 9 ≡ 1 mod 9 kann man relativ leicht bestimmen, weil ja 352 = 360-8 = 9 ⋅ 40 -8 = 9 ⋅ 40 - 9 + 1.

Somit gilt:

(17998 + 352) mod 9 ≡ (7 + 1) mod 9 ≡ 8 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(61 ⋅ 60) mod 8 ≡ (61 mod 8 ⋅ 60 mod 8) mod 8.

61 mod 8 ≡ 5 mod 8 kann man relativ leicht bestimmen, weil ja 61 = 56 + 5 = 7 ⋅ 8 + 5 ist.

60 mod 8 ≡ 4 mod 8 kann man relativ leicht bestimmen, weil ja 60 = 56 + 4 = 7 ⋅ 8 + 4 ist.

Somit gilt:

(61 ⋅ 60) mod 8 ≡ (5 ⋅ 4) mod 8 ≡ 20 mod 8 ≡ 4 mod 8.

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

2: 433²=433¹⁺¹=433¹⋅433¹ ≡ 433⋅433=187489 ≡ 760 mod 929

4: 433⁴=433²⁺²=433²⋅433² ≡ 760⋅760=577600 ≡ 691 mod 929

8: 433⁸=433⁴⁺⁴=433⁴⋅433⁴ ≡ 691⋅691=477481 ≡ 904 mod 929

16: 433¹⁶=433⁸⁺⁸=433⁸⋅433⁸ ≡ 904⋅904=817216 ≡ 625 mod 929

32: 433³²=433¹⁶⁺¹⁶=433¹⁶⋅433¹⁶ ≡ 625⋅625=390625 ≡ 445 mod 929

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

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

247 = 128+64+32+16+4+2+1

150²⁴⁷

= 150^{128+64+32+16+4+2+1}

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

≡ 113 ⋅ 48 ⋅ 294 ⋅ 234 ⋅ 44 ⋅ 277 ⋅ 150 mod 313
≡ 5424 ⋅ 294 ⋅ 234 ⋅ 44 ⋅ 277 ⋅ 150 mod 313 ≡ 103 ⋅ 294 ⋅ 234 ⋅ 44 ⋅ 277 ⋅ 150 mod 313
≡ 30282 ⋅ 234 ⋅ 44 ⋅ 277 ⋅ 150 mod 313 ≡ 234 ⋅ 234 ⋅ 44 ⋅ 277 ⋅ 150 mod 313
≡ 54756 ⋅ 44 ⋅ 277 ⋅ 150 mod 313 ≡ 294 ⋅ 44 ⋅ 277 ⋅ 150 mod 313
≡ 12936 ⋅ 277 ⋅ 150 mod 313 ≡ 103 ⋅ 277 ⋅ 150 mod 313
≡ 28531 ⋅ 150 mod 313 ≡ 48 ⋅ 150 mod 313
≡ 7200 mod 313 ≡ 1 mod 313

Es gilt also: 150²⁴⁷ ≡ 1 mod 313

Berechnung des größten gemeinsamen Teilers von 83 und 46

=>83	= 1⋅46 + 37
=>46	= 1⋅37 + 9
=>37	= 4⋅9 + 1
=>9	= 9⋅1 + 0

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

Es gilt also: ggt(83,46)=1 = 5⋅83 -9⋅46

oder wenn man 5⋅83 auf die linke Seite bringt:

1 -5⋅83 = -9⋅46

-9⋅46 = -5⋅83 + 1 |+83⋅46

-9⋅46 + 83⋅46 = -5⋅83 + 83⋅46 + 1

(-9 + 83) ⋅ 46 = (-5 + 46) ⋅ 83 + 1

74⋅46 = 41⋅83 + 1

Es gilt also: 74⋅46 = 41⋅83 +1

Somit 74⋅46 = 1 mod 83

74 ist also das Inverse von 46 mod 83