Um längere Rechnungen zu vermeiden, rechnen wir:

(2997 + 24002) mod 6 ≡ (2997 mod 6 + 24002 mod 6) mod 6.

2997 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 2997 = 3000-3 = 6 ⋅ 500 -3 = 6 ⋅ 500 - 6 + 3.

24002 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 24002 = 24000+2 = 6 ⋅ 4000 +2.

Somit gilt:

(2997 + 24002) mod 6 ≡ (3 + 2) mod 6 ≡ 5 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(48 ⋅ 96) mod 4 ≡ (48 mod 4 ⋅ 96 mod 4) mod 4.

48 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 48 = 48 + 0 = 12 ⋅ 4 + 0 ist.

96 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 96 = 96 + 0 = 24 ⋅ 4 + 0 ist.

Somit gilt:

(48 ⋅ 96) mod 4 ≡ (0 ⋅ 0) mod 4 ≡ 0 mod 4.

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

2: 230²=230¹⁺¹=230¹⋅230¹ ≡ 230⋅230=52900 ≡ 118 mod 463

4: 230⁴=230²⁺²=230²⋅230² ≡ 118⋅118=13924 ≡ 34 mod 463

8: 230⁸=230⁴⁺⁴=230⁴⋅230⁴ ≡ 34⋅34=1156 ≡ 230 mod 463

16: 230¹⁶=230⁸⁺⁸=230⁸⋅230⁸ ≡ 230⋅230=52900 ≡ 118 mod 463

32: 230³²=230¹⁶⁺¹⁶=230¹⁶⋅230¹⁶ ≡ 118⋅118=13924 ≡ 34 mod 463

64: 230⁶⁴=230³²⁺³²=230³²⋅230³² ≡ 34⋅34=1156 ≡ 230 mod 463

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

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

198 = 128+64+4+2

305¹⁹⁸

= 305^128+64+4+2

= 305¹²⁸⋅305⁶⁴⋅305⁴⋅305²

≡ 73 ⋅ 87 ⋅ 243 ⋅ 262 mod 937
≡ 6351 ⋅ 243 ⋅ 262 mod 937 ≡ 729 ⋅ 243 ⋅ 262 mod 937
≡ 177147 ⋅ 262 mod 937 ≡ 54 ⋅ 262 mod 937
≡ 14148 mod 937 ≡ 93 mod 937

Es gilt also: 305¹⁹⁸ ≡ 93 mod 937

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

=>73	= 1⋅48 + 25
=>48	= 1⋅25 + 23
=>25	= 1⋅23 + 2
=>23	= 11⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(73,48)=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= 23-11⋅2
2= 25-1⋅23	eingesetzt in die Zeile drüber:	1	= 1⋅23 -11⋅(25 -1⋅ 23) = 1⋅23 -11⋅25 +11⋅ 23) = -11⋅25 +12⋅ 23 (=1)
23= 48-1⋅25	eingesetzt in die Zeile drüber:	1	= -11⋅25 +12⋅(48 -1⋅ 25) = -11⋅25 +12⋅48 -12⋅ 25) = 12⋅48 -23⋅ 25 (=1)
25= 73-1⋅48	eingesetzt in die Zeile drüber:	1	= 12⋅48 -23⋅(73 -1⋅ 48) = 12⋅48 -23⋅73 +23⋅ 48) = -23⋅73 +35⋅ 48 (=1)

Es gilt also: ggt(73,48)=1 = -23⋅73 +35⋅48

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

1 +23⋅73 = +35⋅48

Es gilt also: 35⋅48 = 23⋅73 +1

Somit 35⋅48 = 1 mod 73

35 ist also das Inverse von 48 mod 73