Um längere Rechnungen zu vermeiden, rechnen wir:

(27999 + 1407) mod 7 ≡ (27999 mod 7 + 1407 mod 7) mod 7.

27999 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 27999 = 28000-1 = 7 ⋅ 4000 -1 = 7 ⋅ 4000 - 7 + 6.

1407 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 1407 = 1400+7 = 7 ⋅ 200 +7.

Somit gilt:

(27999 + 1407) mod 7 ≡ (6 + 0) mod 7 ≡ 6 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(71 ⋅ 67) mod 10 ≡ (71 mod 10 ⋅ 67 mod 10) mod 10.

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

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

Somit gilt:

(71 ⋅ 67) mod 10 ≡ (1 ⋅ 7) mod 10 ≡ 7 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: 284¹=284

2: 284²=284¹⁺¹=284¹⋅284¹ ≡ 284⋅284=80656 ≡ 245 mod 421

4: 284⁴=284²⁺²=284²⋅284² ≡ 245⋅245=60025 ≡ 243 mod 421

8: 284⁸=284⁴⁺⁴=284⁴⋅284⁴ ≡ 243⋅243=59049 ≡ 109 mod 421

16: 284¹⁶=284⁸⁺⁸=284⁸⋅284⁸ ≡ 109⋅109=11881 ≡ 93 mod 421

32: 284³²=284¹⁶⁺¹⁶=284¹⁶⋅284¹⁶ ≡ 93⋅93=8649 ≡ 229 mod 421

64: 284⁶⁴=284³²⁺³²=284³²⋅284³² ≡ 229⋅229=52441 ≡ 237 mod 421

128: 284¹²⁸=284⁶⁴⁺⁶⁴=284⁶⁴⋅284⁶⁴ ≡ 237⋅237=56169 ≡ 176 mod 421

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

563¹⁹⁸

= 563^128+64+4+2

= 563¹²⁸⋅563⁶⁴⋅563⁴⋅563²

≡ 637 ⋅ 479 ⋅ 123 ⋅ 291 mod 829
≡ 305123 ⋅ 123 ⋅ 291 mod 829 ≡ 51 ⋅ 123 ⋅ 291 mod 829
≡ 6273 ⋅ 291 mod 829 ≡ 470 ⋅ 291 mod 829
≡ 136770 mod 829 ≡ 814 mod 829

Es gilt also: 563¹⁹⁸ ≡ 814 mod 829

Berechnung des größten gemeinsamen Teilers von 89 und 42

=>89	= 2⋅42 + 5
=>42	= 8⋅5 + 2
=>5	= 2⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(89,42)=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= 42-8⋅5	eingesetzt in die Zeile drüber:	1	= 1⋅5 -2⋅(42 -8⋅ 5) = 1⋅5 -2⋅42 +16⋅ 5) = -2⋅42 +17⋅ 5 (=1)
5= 89-2⋅42	eingesetzt in die Zeile drüber:	1	= -2⋅42 +17⋅(89 -2⋅ 42) = -2⋅42 +17⋅89 -34⋅ 42) = 17⋅89 -36⋅ 42 (=1)

Es gilt also: ggt(89,42)=1 = 17⋅89 -36⋅42

oder wenn man 17⋅89 auf die linke Seite bringt:

1 -17⋅89 = -36⋅42

-36⋅42 = -17⋅89 + 1 |+89⋅42

-36⋅42 + 89⋅42 = -17⋅89 + 89⋅42 + 1

(-36 + 89) ⋅ 42 = (-17 + 42) ⋅ 89 + 1

53⋅42 = 25⋅89 + 1

Es gilt also: 53⋅42 = 25⋅89 +1

Somit 53⋅42 = 1 mod 89

53 ist also das Inverse von 42 mod 89