Um längere Rechnungen zu vermeiden, rechnen wir:

(68 + 279) mod 7 ≡ (68 mod 7 + 279 mod 7) mod 7.

68 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 68 = 70-2 = 7 ⋅ 10 -2 = 7 ⋅ 10 - 7 + 5.

279 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 279 = 280-1 = 7 ⋅ 40 -1 = 7 ⋅ 40 - 7 + 6.

Somit gilt:

(68 + 279) mod 7 ≡ (5 + 6) mod 7 ≡ 11 mod 7 ≡ 4 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(80 ⋅ 56) mod 5 ≡ (80 mod 5 ⋅ 56 mod 5) mod 5.

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

56 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 56 = 55 + 1 = 11 ⋅ 5 + 1 ist.

Somit gilt:

(80 ⋅ 56) mod 5 ≡ (0 ⋅ 1) mod 5 ≡ 0 mod 5.

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

2: 589²=589¹⁺¹=589¹⋅589¹ ≡ 589⋅589=346921 ≡ 363 mod 719

4: 589⁴=589²⁺²=589²⋅589² ≡ 363⋅363=131769 ≡ 192 mod 719

8: 589⁸=589⁴⁺⁴=589⁴⋅589⁴ ≡ 192⋅192=36864 ≡ 195 mod 719

16: 589¹⁶=589⁸⁺⁸=589⁸⋅589⁸ ≡ 195⋅195=38025 ≡ 637 mod 719

32: 589³²=589¹⁶⁺¹⁶=589¹⁶⋅589¹⁶ ≡ 637⋅637=405769 ≡ 253 mod 719

64: 589⁶⁴=589³²⁺³²=589³²⋅589³² ≡ 253⋅253=64009 ≡ 18 mod 719

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

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

207 = 128+64+8+4+2+1

406²⁰⁷

= 406^{128+64+8+4+2+1}

= 406¹²⁸⋅406⁶⁴⋅406⁸⋅406⁴⋅406²⋅406¹

≡ 296 ⋅ 27 ⋅ 417 ⋅ 150 ⋅ 296 ⋅ 406 mod 433
≡ 7992 ⋅ 417 ⋅ 150 ⋅ 296 ⋅ 406 mod 433 ≡ 198 ⋅ 417 ⋅ 150 ⋅ 296 ⋅ 406 mod 433
≡ 82566 ⋅ 150 ⋅ 296 ⋅ 406 mod 433 ≡ 296 ⋅ 150 ⋅ 296 ⋅ 406 mod 433
≡ 44400 ⋅ 296 ⋅ 406 mod 433 ≡ 234 ⋅ 296 ⋅ 406 mod 433
≡ 69264 ⋅ 406 mod 433 ≡ 417 ⋅ 406 mod 433
≡ 169302 mod 433 ≡ 432 mod 433

Es gilt also: 406²⁰⁷ ≡ 432 mod 433

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

=>89	= 1⋅79 + 10
=>79	= 7⋅10 + 9
=>10	= 1⋅9 + 1
=>9	= 9⋅1 + 0

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

Es gilt also: ggt(89,79)=1 = 8⋅89 -9⋅79

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

1 -8⋅89 = -9⋅79

-9⋅79 = -8⋅89 + 1 |+89⋅79

-9⋅79 + 89⋅79 = -8⋅89 + 89⋅79 + 1

(-9 + 89) ⋅ 79 = (-8 + 79) ⋅ 89 + 1

80⋅79 = 71⋅89 + 1

Es gilt also: 80⋅79 = 71⋅89 +1

Somit 80⋅79 = 1 mod 89

80 ist also das Inverse von 79 mod 89