Um längere Rechnungen zu vermeiden, rechnen wir:

(298 - 8999) mod 3 ≡ (298 mod 3 - 8999 mod 3) mod 3.

298 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 298 = 300-2 = 3 ⋅ 100 -2 = 3 ⋅ 100 - 3 + 1.

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

Somit gilt:

(298 - 8999) mod 3 ≡ (1 - 2) mod 3 ≡ -1 mod 3 ≡ 2 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(38 ⋅ 94) mod 9 ≡ (38 mod 9 ⋅ 94 mod 9) mod 9.

38 mod 9 ≡ 2 mod 9 kann man relativ leicht bestimmen, weil ja 38 = 36 + 2 = 4 ⋅ 9 + 2 ist.

94 mod 9 ≡ 4 mod 9 kann man relativ leicht bestimmen, weil ja 94 = 90 + 4 = 10 ⋅ 9 + 4 ist.

Somit gilt:

(38 ⋅ 94) mod 9 ≡ (2 ⋅ 4) mod 9 ≡ 8 mod 9.

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

2: 213²=213¹⁺¹=213¹⋅213¹ ≡ 213⋅213=45369 ≡ 100 mod 223

4: 213⁴=213²⁺²=213²⋅213² ≡ 100⋅100=10000 ≡ 188 mod 223

8: 213⁸=213⁴⁺⁴=213⁴⋅213⁴ ≡ 188⋅188=35344 ≡ 110 mod 223

16: 213¹⁶=213⁸⁺⁸=213⁸⋅213⁸ ≡ 110⋅110=12100 ≡ 58 mod 223

32: 213³²=213¹⁶⁺¹⁶=213¹⁶⋅213¹⁶ ≡ 58⋅58=3364 ≡ 19 mod 223

64: 213⁶⁴=213³²⁺³²=213³²⋅213³² ≡ 19⋅19=361 ≡ 138 mod 223

128: 213¹²⁸=213⁶⁴⁺⁶⁴=213⁶⁴⋅213⁶⁴ ≡ 138⋅138=19044 ≡ 89 mod 223

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

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

206 = 128+64+8+4+2

200²⁰⁶

= 200^128+64+8+4+2

= 200¹²⁸⋅200⁶⁴⋅200⁸⋅200⁴⋅200²

≡ 544 ⋅ 378 ⋅ 548 ⋅ 56 ⋅ 533 mod 647
≡ 205632 ⋅ 548 ⋅ 56 ⋅ 533 mod 647 ≡ 533 ⋅ 548 ⋅ 56 ⋅ 533 mod 647
≡ 292084 ⋅ 56 ⋅ 533 mod 647 ≡ 287 ⋅ 56 ⋅ 533 mod 647
≡ 16072 ⋅ 533 mod 647 ≡ 544 ⋅ 533 mod 647
≡ 289952 mod 647 ≡ 96 mod 647

Es gilt also: 200²⁰⁶ ≡ 96 mod 647

Berechnung des größten gemeinsamen Teilers von 73 und 32

=>73	= 2⋅32 + 9
=>32	= 3⋅9 + 5
=>9	= 1⋅5 + 4
=>5	= 1⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(73,32)=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= 5-1⋅4
4= 9-1⋅5	eingesetzt in die Zeile drüber:	1	= 1⋅5 -1⋅(9 -1⋅ 5) = 1⋅5 -1⋅9 +1⋅ 5) = -1⋅9 +2⋅ 5 (=1)
5= 32-3⋅9	eingesetzt in die Zeile drüber:	1	= -1⋅9 +2⋅(32 -3⋅ 9) = -1⋅9 +2⋅32 -6⋅ 9) = 2⋅32 -7⋅ 9 (=1)
9= 73-2⋅32	eingesetzt in die Zeile drüber:	1	= 2⋅32 -7⋅(73 -2⋅ 32) = 2⋅32 -7⋅73 +14⋅ 32) = -7⋅73 +16⋅ 32 (=1)

Es gilt also: ggt(73,32)=1 = -7⋅73 +16⋅32

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

1 +7⋅73 = +16⋅32

Es gilt also: 16⋅32 = 7⋅73 +1

Somit 16⋅32 = 1 mod 73

16 ist also das Inverse von 32 mod 73