Um längere Rechnungen zu vermeiden, rechnen wir:

(8998 + 903) mod 3 ≡ (8998 mod 3 + 903 mod 3) mod 3.

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

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

Somit gilt:

(8998 + 903) mod 3 ≡ (1 + 0) mod 3 ≡ 1 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(85 ⋅ 68) mod 8 ≡ (85 mod 8 ⋅ 68 mod 8) mod 8.

85 mod 8 ≡ 5 mod 8 kann man relativ leicht bestimmen, weil ja 85 = 80 + 5 = 10 ⋅ 8 + 5 ist.

68 mod 8 ≡ 4 mod 8 kann man relativ leicht bestimmen, weil ja 68 = 64 + 4 = 8 ⋅ 8 + 4 ist.

Somit gilt:

(85 ⋅ 68) mod 8 ≡ (5 ⋅ 4) mod 8 ≡ 20 mod 8 ≡ 4 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: 613¹=613

2: 613²=613¹⁺¹=613¹⋅613¹ ≡ 613⋅613=375769 ≡ 573 mod 967

4: 613⁴=613²⁺²=613²⋅613² ≡ 573⋅573=328329 ≡ 516 mod 967

8: 613⁸=613⁴⁺⁴=613⁴⋅613⁴ ≡ 516⋅516=266256 ≡ 331 mod 967

16: 613¹⁶=613⁸⁺⁸=613⁸⋅613⁸ ≡ 331⋅331=109561 ≡ 290 mod 967

32: 613³²=613¹⁶⁺¹⁶=613¹⁶⋅613¹⁶ ≡ 290⋅290=84100 ≡ 938 mod 967

64: 613⁶⁴=613³²⁺³²=613³²⋅613³² ≡ 938⋅938=879844 ≡ 841 mod 967

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

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

122 = 64+32+16+8+2

156¹²²

= 156^64+32+16+8+2

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

≡ 200 ⋅ 48 ⋅ 92 ⋅ 108 ⋅ 140 mod 263
≡ 9600 ⋅ 92 ⋅ 108 ⋅ 140 mod 263 ≡ 132 ⋅ 92 ⋅ 108 ⋅ 140 mod 263
≡ 12144 ⋅ 108 ⋅ 140 mod 263 ≡ 46 ⋅ 108 ⋅ 140 mod 263
≡ 4968 ⋅ 140 mod 263 ≡ 234 ⋅ 140 mod 263
≡ 32760 mod 263 ≡ 148 mod 263

Es gilt also: 156¹²² ≡ 148 mod 263

Berechnung des größten gemeinsamen Teilers von 53 und 30

=>53	= 1⋅30 + 23
=>30	= 1⋅23 + 7
=>23	= 3⋅7 + 2
=>7	= 3⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(53,30)=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= 7-3⋅2
2= 23-3⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -3⋅(23 -3⋅ 7) = 1⋅7 -3⋅23 +9⋅ 7) = -3⋅23 +10⋅ 7 (=1)
7= 30-1⋅23	eingesetzt in die Zeile drüber:	1	= -3⋅23 +10⋅(30 -1⋅ 23) = -3⋅23 +10⋅30 -10⋅ 23) = 10⋅30 -13⋅ 23 (=1)
23= 53-1⋅30	eingesetzt in die Zeile drüber:	1	= 10⋅30 -13⋅(53 -1⋅ 30) = 10⋅30 -13⋅53 +13⋅ 30) = -13⋅53 +23⋅ 30 (=1)

Es gilt also: ggt(53,30)=1 = -13⋅53 +23⋅30

oder wenn man -13⋅53 auf die linke Seite bringt:

1 +13⋅53 = +23⋅30

Es gilt also: 23⋅30 = 13⋅53 +1

Somit 23⋅30 = 1 mod 53

23 ist also das Inverse von 30 mod 53