Um längere Rechnungen zu vermeiden, rechnen wir:

(118 - 5997) mod 3 ≡ (118 mod 3 - 5997 mod 3) mod 3.

118 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 118 = 120-2 = 3 ⋅ 40 -2 = 3 ⋅ 40 - 3 + 1.

5997 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 5997 = 6000-3 = 3 ⋅ 2000 -3 = 3 ⋅ 2000 - 3 + 0.

Somit gilt:

(118 - 5997) mod 3 ≡ (1 - 0) mod 3 ≡ 1 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(97 ⋅ 73) mod 8 ≡ (97 mod 8 ⋅ 73 mod 8) mod 8.

97 mod 8 ≡ 1 mod 8 kann man relativ leicht bestimmen, weil ja 97 = 96 + 1 = 12 ⋅ 8 + 1 ist.

73 mod 8 ≡ 1 mod 8 kann man relativ leicht bestimmen, weil ja 73 = 72 + 1 = 9 ⋅ 8 + 1 ist.

Somit gilt:

(97 ⋅ 73) mod 8 ≡ (1 ⋅ 1) mod 8 ≡ 1 mod 8.

Die 64 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: 209¹=209

2: 209²=209¹⁺¹=209¹⋅209¹ ≡ 209⋅209=43681 ≡ 416 mod 509

4: 209⁴=209²⁺²=209²⋅209² ≡ 416⋅416=173056 ≡ 505 mod 509

8: 209⁸=209⁴⁺⁴=209⁴⋅209⁴ ≡ 505⋅505=255025 ≡ 16 mod 509

16: 209¹⁶=209⁸⁺⁸=209⁸⋅209⁸ ≡ 16⋅16=256 ≡ 256 mod 509

32: 209³²=209¹⁶⁺¹⁶=209¹⁶⋅209¹⁶ ≡ 256⋅256=65536 ≡ 384 mod 509

64: 209⁶⁴=209³²⁺³²=209³²⋅209³² ≡ 384⋅384=147456 ≡ 355 mod 509

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

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

233 = 128+64+32+8+1

984²³³

= 984^{128+64+32+8+1}

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

≡ 171 ⋅ 519 ⋅ 705 ⋅ 276 ⋅ 984 mod 997
≡ 88749 ⋅ 705 ⋅ 276 ⋅ 984 mod 997 ≡ 16 ⋅ 705 ⋅ 276 ⋅ 984 mod 997
≡ 11280 ⋅ 276 ⋅ 984 mod 997 ≡ 313 ⋅ 276 ⋅ 984 mod 997
≡ 86388 ⋅ 984 mod 997 ≡ 646 ⋅ 984 mod 997
≡ 635664 mod 997 ≡ 575 mod 997

Es gilt also: 984²³³ ≡ 575 mod 997

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

=>101	= 2⋅41 + 19
=>41	= 2⋅19 + 3
=>19	= 6⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(101,41)=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= 19-6⋅3
3= 41-2⋅19	eingesetzt in die Zeile drüber:	1	= 1⋅19 -6⋅(41 -2⋅ 19) = 1⋅19 -6⋅41 +12⋅ 19) = -6⋅41 +13⋅ 19 (=1)
19= 101-2⋅41	eingesetzt in die Zeile drüber:	1	= -6⋅41 +13⋅(101 -2⋅ 41) = -6⋅41 +13⋅101 -26⋅ 41) = 13⋅101 -32⋅ 41 (=1)

Es gilt also: ggt(101,41)=1 = 13⋅101 -32⋅41

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

1 -13⋅101 = -32⋅41

-32⋅41 = -13⋅101 + 1 |+101⋅41

-32⋅41 + 101⋅41 = -13⋅101 + 101⋅41 + 1

(-32 + 101) ⋅ 41 = (-13 + 41) ⋅ 101 + 1

69⋅41 = 28⋅101 + 1

Es gilt also: 69⋅41 = 28⋅101 +1

Somit 69⋅41 = 1 mod 101

69 ist also das Inverse von 41 mod 101