Um längere Rechnungen zu vermeiden, rechnen wir:

(11994 + 6001) mod 6 ≡ (11994 mod 6 + 6001 mod 6) mod 6.

11994 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 11994 = 12000-6 = 6 ⋅ 2000 -6 = 6 ⋅ 2000 - 6 + 0.

6001 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 6001 = 6000+1 = 6 ⋅ 1000 +1.

Somit gilt:

(11994 + 6001) mod 6 ≡ (0 + 1) mod 6 ≡ 1 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(76 ⋅ 95) mod 10 ≡ (76 mod 10 ⋅ 95 mod 10) mod 10.

76 mod 10 ≡ 6 mod 10 kann man relativ leicht bestimmen, weil ja 76 = 70 + 6 = 7 ⋅ 10 + 6 ist.

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

Somit gilt:

(76 ⋅ 95) mod 10 ≡ (6 ⋅ 5) mod 10 ≡ 30 mod 10 ≡ 0 mod 10.

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

2: 215²=215¹⁺¹=215¹⋅215¹ ≡ 215⋅215=46225 ≡ 366 mod 379

4: 215⁴=215²⁺²=215²⋅215² ≡ 366⋅366=133956 ≡ 169 mod 379

8: 215⁸=215⁴⁺⁴=215⁴⋅215⁴ ≡ 169⋅169=28561 ≡ 136 mod 379

16: 215¹⁶=215⁸⁺⁸=215⁸⋅215⁸ ≡ 136⋅136=18496 ≡ 304 mod 379

32: 215³²=215¹⁶⁺¹⁶=215¹⁶⋅215¹⁶ ≡ 304⋅304=92416 ≡ 319 mod 379

64: 215⁶⁴=215³²⁺³²=215³²⋅215³² ≡ 319⋅319=101761 ≡ 189 mod 379

128: 215¹²⁸=215⁶⁴⁺⁶⁴=215⁶⁴⋅215⁶⁴ ≡ 189⋅189=35721 ≡ 95 mod 379

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

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

229 = 128+64+32+4+1

600²²⁹

= 600^{128+64+32+4+1}

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

≡ 570 ⋅ 379 ⋅ 93 ⋅ 519 ⋅ 600 mod 827
≡ 216030 ⋅ 93 ⋅ 519 ⋅ 600 mod 827 ≡ 183 ⋅ 93 ⋅ 519 ⋅ 600 mod 827
≡ 17019 ⋅ 519 ⋅ 600 mod 827 ≡ 479 ⋅ 519 ⋅ 600 mod 827
≡ 248601 ⋅ 600 mod 827 ≡ 501 ⋅ 600 mod 827
≡ 300600 mod 827 ≡ 399 mod 827

Es gilt also: 600²²⁹ ≡ 399 mod 827

Berechnung des größten gemeinsamen Teilers von 61 und 22

=>61	= 2⋅22 + 17
=>22	= 1⋅17 + 5
=>17	= 3⋅5 + 2
=>5	= 2⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(61,22)=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-2⋅2
2= 17-3⋅5	eingesetzt in die Zeile drüber:	1	= 1⋅5 -2⋅(17 -3⋅ 5) = 1⋅5 -2⋅17 +6⋅ 5) = -2⋅17 +7⋅ 5 (=1)
5= 22-1⋅17	eingesetzt in die Zeile drüber:	1	= -2⋅17 +7⋅(22 -1⋅ 17) = -2⋅17 +7⋅22 -7⋅ 17) = 7⋅22 -9⋅ 17 (=1)
17= 61-2⋅22	eingesetzt in die Zeile drüber:	1	= 7⋅22 -9⋅(61 -2⋅ 22) = 7⋅22 -9⋅61 +18⋅ 22) = -9⋅61 +25⋅ 22 (=1)

Es gilt also: ggt(61,22)=1 = -9⋅61 +25⋅22

oder wenn man -9⋅61 auf die linke Seite bringt:

1 +9⋅61 = +25⋅22

Es gilt also: 25⋅22 = 9⋅61 +1

Somit 25⋅22 = 1 mod 61

25 ist also das Inverse von 22 mod 61