Um längere Rechnungen zu vermeiden, rechnen wir:

(27994 - 7002) mod 7 ≡ (27994 mod 7 - 7002 mod 7) mod 7.

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

7002 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 7002 = 7000+2 = 7 ⋅ 1000 +2.

Somit gilt:

(27994 - 7002) mod 7 ≡ (1 - 2) mod 7 ≡ -1 mod 7 ≡ 6 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(28 ⋅ 52) mod 10 ≡ (28 mod 10 ⋅ 52 mod 10) mod 10.

28 mod 10 ≡ 8 mod 10 kann man relativ leicht bestimmen, weil ja 28 = 20 + 8 = 2 ⋅ 10 + 8 ist.

52 mod 10 ≡ 2 mod 10 kann man relativ leicht bestimmen, weil ja 52 = 50 + 2 = 5 ⋅ 10 + 2 ist.

Somit gilt:

(28 ⋅ 52) mod 10 ≡ (8 ⋅ 2) mod 10 ≡ 16 mod 10 ≡ 6 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: 289¹=289

2: 289²=289¹⁺¹=289¹⋅289¹ ≡ 289⋅289=83521 ≡ 229 mod 631

4: 289⁴=289²⁺²=289²⋅289² ≡ 229⋅229=52441 ≡ 68 mod 631

8: 289⁸=289⁴⁺⁴=289⁴⋅289⁴ ≡ 68⋅68=4624 ≡ 207 mod 631

16: 289¹⁶=289⁸⁺⁸=289⁸⋅289⁸ ≡ 207⋅207=42849 ≡ 572 mod 631

32: 289³²=289¹⁶⁺¹⁶=289¹⁶⋅289¹⁶ ≡ 572⋅572=327184 ≡ 326 mod 631

64: 289⁶⁴=289³²⁺³²=289³²⋅289³² ≡ 326⋅326=106276 ≡ 268 mod 631

128: 289¹²⁸=289⁶⁴⁺⁶⁴=289⁶⁴⋅289⁶⁴ ≡ 268⋅268=71824 ≡ 521 mod 631

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

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

83 = 64+16+2+1

348⁸³

= 348^64+16+2+1

= 348⁶⁴⋅348¹⁶⋅348²⋅348¹

≡ 107 ⋅ 217 ⋅ 115 ⋅ 348 mod 647
≡ 23219 ⋅ 115 ⋅ 348 mod 647 ≡ 574 ⋅ 115 ⋅ 348 mod 647
≡ 66010 ⋅ 348 mod 647 ≡ 16 ⋅ 348 mod 647
≡ 5568 mod 647 ≡ 392 mod 647

Es gilt also: 348⁸³ ≡ 392 mod 647

Berechnung des größten gemeinsamen Teilers von 59 und 56

=>59	= 1⋅56 + 3
=>56	= 18⋅3 + 2
=>3	= 1⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(59,56)=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= 3-1⋅2
2= 56-18⋅3	eingesetzt in die Zeile drüber:	1	= 1⋅3 -1⋅(56 -18⋅ 3) = 1⋅3 -1⋅56 +18⋅ 3) = -1⋅56 +19⋅ 3 (=1)
3= 59-1⋅56	eingesetzt in die Zeile drüber:	1	= -1⋅56 +19⋅(59 -1⋅ 56) = -1⋅56 +19⋅59 -19⋅ 56) = 19⋅59 -20⋅ 56 (=1)

Es gilt also: ggt(59,56)=1 = 19⋅59 -20⋅56

oder wenn man 19⋅59 auf die linke Seite bringt:

1 -19⋅59 = -20⋅56

-20⋅56 = -19⋅59 + 1 |+59⋅56

-20⋅56 + 59⋅56 = -19⋅59 + 59⋅56 + 1

(-20 + 59) ⋅ 56 = (-19 + 56) ⋅ 59 + 1

39⋅56 = 37⋅59 + 1

Es gilt also: 39⋅56 = 37⋅59 +1

Somit 39⋅56 = 1 mod 59

39 ist also das Inverse von 56 mod 59