Um längere Rechnungen zu vermeiden, rechnen wir:

(48 + 25000) mod 5 ≡ (48 mod 5 + 25000 mod 5) mod 5.

48 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 48 = 40+8 = 5 ⋅ 8 +8.

25000 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 25000 = 25000+0 = 5 ⋅ 5000 +0.

Somit gilt:

(48 + 25000) mod 5 ≡ (3 + 0) mod 5 ≡ 3 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(39 ⋅ 53) mod 7 ≡ (39 mod 7 ⋅ 53 mod 7) mod 7.

39 mod 7 ≡ 4 mod 7 kann man relativ leicht bestimmen, weil ja 39 = 35 + 4 = 5 ⋅ 7 + 4 ist.

53 mod 7 ≡ 4 mod 7 kann man relativ leicht bestimmen, weil ja 53 = 49 + 4 = 7 ⋅ 7 + 4 ist.

Somit gilt:

(39 ⋅ 53) mod 7 ≡ (4 ⋅ 4) mod 7 ≡ 16 mod 7 ≡ 2 mod 7.

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

2: 610²=610¹⁺¹=610¹⋅610¹ ≡ 610⋅610=372100 ≡ 287 mod 773

4: 610⁴=610²⁺²=610²⋅610² ≡ 287⋅287=82369 ≡ 431 mod 773

8: 610⁸=610⁴⁺⁴=610⁴⋅610⁴ ≡ 431⋅431=185761 ≡ 241 mod 773

16: 610¹⁶=610⁸⁺⁸=610⁸⋅610⁸ ≡ 241⋅241=58081 ≡ 106 mod 773

32: 610³²=610¹⁶⁺¹⁶=610¹⁶⋅610¹⁶ ≡ 106⋅106=11236 ≡ 414 mod 773

64: 610⁶⁴=610³²⁺³²=610³²⋅610³² ≡ 414⋅414=171396 ≡ 563 mod 773

128: 610¹²⁸=610⁶⁴⁺⁶⁴=610⁶⁴⋅610⁶⁴ ≡ 563⋅563=316969 ≡ 39 mod 773

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

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

189 = 128+32+16+8+4+1

668¹⁸⁹

= 668^{128+32+16+8+4+1}

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

≡ 337 ⋅ 36 ⋅ 6 ⋅ 757 ⋅ 449 ⋅ 668 mod 797
≡ 12132 ⋅ 6 ⋅ 757 ⋅ 449 ⋅ 668 mod 797 ≡ 177 ⋅ 6 ⋅ 757 ⋅ 449 ⋅ 668 mod 797
≡ 1062 ⋅ 757 ⋅ 449 ⋅ 668 mod 797 ≡ 265 ⋅ 757 ⋅ 449 ⋅ 668 mod 797
≡ 200605 ⋅ 449 ⋅ 668 mod 797 ≡ 558 ⋅ 449 ⋅ 668 mod 797
≡ 250542 ⋅ 668 mod 797 ≡ 284 ⋅ 668 mod 797
≡ 189712 mod 797 ≡ 26 mod 797

Es gilt also: 668¹⁸⁹ ≡ 26 mod 797

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

=>79	= 2⋅32 + 15
=>32	= 2⋅15 + 2
=>15	= 7⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(79,32)=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= 15-7⋅2
2= 32-2⋅15	eingesetzt in die Zeile drüber:	1	= 1⋅15 -7⋅(32 -2⋅ 15) = 1⋅15 -7⋅32 +14⋅ 15) = -7⋅32 +15⋅ 15 (=1)
15= 79-2⋅32	eingesetzt in die Zeile drüber:	1	= -7⋅32 +15⋅(79 -2⋅ 32) = -7⋅32 +15⋅79 -30⋅ 32) = 15⋅79 -37⋅ 32 (=1)

Es gilt also: ggt(79,32)=1 = 15⋅79 -37⋅32

oder wenn man 15⋅79 auf die linke Seite bringt:

1 -15⋅79 = -37⋅32

-37⋅32 = -15⋅79 + 1 |+79⋅32

-37⋅32 + 79⋅32 = -15⋅79 + 79⋅32 + 1

(-37 + 79) ⋅ 32 = (-15 + 32) ⋅ 79 + 1

42⋅32 = 17⋅79 + 1

Es gilt also: 42⋅32 = 17⋅79 +1

Somit 42⋅32 = 1 mod 79

42 ist also das Inverse von 32 mod 79