Um längere Rechnungen zu vermeiden, rechnen wir:

(364 + 2700) mod 9 ≡ (364 mod 9 + 2700 mod 9) mod 9.

364 mod 9 ≡ 4 mod 9 kann man relativ leicht bestimmen, weil ja 364 = 360+4 = 9 ⋅ 40 +4.

2700 mod 9 ≡ 0 mod 9 kann man relativ leicht bestimmen, weil ja 2700 = 2700+0 = 9 ⋅ 300 +0.

Somit gilt:

(364 + 2700) mod 9 ≡ (4 + 0) mod 9 ≡ 4 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(74 ⋅ 90) mod 5 ≡ (74 mod 5 ⋅ 90 mod 5) mod 5.

74 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 74 = 70 + 4 = 14 ⋅ 5 + 4 ist.

90 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 90 = 90 + 0 = 18 ⋅ 5 + 0 ist.

Somit gilt:

(74 ⋅ 90) mod 5 ≡ (4 ⋅ 0) mod 5 ≡ 0 mod 5.

Die 16 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: 154¹=154

2: 154²=154¹⁺¹=154¹⋅154¹ ≡ 154⋅154=23716 ≡ 333 mod 349

4: 154⁴=154²⁺²=154²⋅154² ≡ 333⋅333=110889 ≡ 256 mod 349

8: 154⁸=154⁴⁺⁴=154⁴⋅154⁴ ≡ 256⋅256=65536 ≡ 273 mod 349

16: 154¹⁶=154⁸⁺⁸=154⁸⋅154⁸ ≡ 273⋅273=74529 ≡ 192 mod 349

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

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

254 = 128+64+32+16+8+4+2

399²⁵⁴

= 399^{128+64+32+16+8+4+2}

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

≡ 441 ⋅ 500 ⋅ 427 ⋅ 352 ⋅ 450 ⋅ 88 ⋅ 296 mod 521
≡ 220500 ⋅ 427 ⋅ 352 ⋅ 450 ⋅ 88 ⋅ 296 mod 521 ≡ 117 ⋅ 427 ⋅ 352 ⋅ 450 ⋅ 88 ⋅ 296 mod 521
≡ 49959 ⋅ 352 ⋅ 450 ⋅ 88 ⋅ 296 mod 521 ≡ 464 ⋅ 352 ⋅ 450 ⋅ 88 ⋅ 296 mod 521
≡ 163328 ⋅ 450 ⋅ 88 ⋅ 296 mod 521 ≡ 255 ⋅ 450 ⋅ 88 ⋅ 296 mod 521
≡ 114750 ⋅ 88 ⋅ 296 mod 521 ≡ 130 ⋅ 88 ⋅ 296 mod 521
≡ 11440 ⋅ 296 mod 521 ≡ 499 ⋅ 296 mod 521
≡ 147704 mod 521 ≡ 261 mod 521

Es gilt also: 399²⁵⁴ ≡ 261 mod 521

Berechnung des größten gemeinsamen Teilers von 79 und 44

=>79	= 1⋅44 + 35
=>44	= 1⋅35 + 9
=>35	= 3⋅9 + 8
=>9	= 1⋅8 + 1
=>8	= 8⋅1 + 0

also gilt: ggt(79,44)=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= 9-1⋅8
8= 35-3⋅9	eingesetzt in die Zeile drüber:	1	= 1⋅9 -1⋅(35 -3⋅ 9) = 1⋅9 -1⋅35 +3⋅ 9) = -1⋅35 +4⋅ 9 (=1)
9= 44-1⋅35	eingesetzt in die Zeile drüber:	1	= -1⋅35 +4⋅(44 -1⋅ 35) = -1⋅35 +4⋅44 -4⋅ 35) = 4⋅44 -5⋅ 35 (=1)
35= 79-1⋅44	eingesetzt in die Zeile drüber:	1	= 4⋅44 -5⋅(79 -1⋅ 44) = 4⋅44 -5⋅79 +5⋅ 44) = -5⋅79 +9⋅ 44 (=1)

Es gilt also: ggt(79,44)=1 = -5⋅79 +9⋅44

oder wenn man -5⋅79 auf die linke Seite bringt:

1 +5⋅79 = +9⋅44

Es gilt also: 9⋅44 = 5⋅79 +1

Somit 9⋅44 = 1 mod 79

9 ist also das Inverse von 44 mod 79