Um längere Rechnungen zu vermeiden, rechnen wir:

(320 + 23998) mod 8 ≡ (320 mod 8 + 23998 mod 8) mod 8.

320 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 320 = 320+0 = 8 ⋅ 40 +0.

23998 mod 8 ≡ 6 mod 8 kann man relativ leicht bestimmen, weil ja 23998 = 23000+998 = 8 ⋅ 2875 +998.

Somit gilt:

(320 + 23998) mod 8 ≡ (0 + 6) mod 8 ≡ 6 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(70 ⋅ 24) mod 6 ≡ (70 mod 6 ⋅ 24 mod 6) mod 6.

70 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 70 = 66 + 4 = 11 ⋅ 6 + 4 ist.

24 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 24 = 24 + 0 = 4 ⋅ 6 + 0 ist.

Somit gilt:

(70 ⋅ 24) mod 6 ≡ (4 ⋅ 0) mod 6 ≡ 0 mod 6.

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

2: 661²=661¹⁺¹=661¹⋅661¹ ≡ 661⋅661=436921 ≡ 172 mod 739

4: 661⁴=661²⁺²=661²⋅661² ≡ 172⋅172=29584 ≡ 24 mod 739

8: 661⁸=661⁴⁺⁴=661⁴⋅661⁴ ≡ 24⋅24=576 ≡ 576 mod 739

16: 661¹⁶=661⁸⁺⁸=661⁸⋅661⁸ ≡ 576⋅576=331776 ≡ 704 mod 739

32: 661³²=661¹⁶⁺¹⁶=661¹⁶⋅661¹⁶ ≡ 704⋅704=495616 ≡ 486 mod 739

64: 661⁶⁴=661³²⁺³²=661³²⋅661³² ≡ 486⋅486=236196 ≡ 455 mod 739

128: 661¹²⁸=661⁶⁴⁺⁶⁴=661⁶⁴⋅661⁶⁴ ≡ 455⋅455=207025 ≡ 105 mod 739

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

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

101 = 64+32+4+1

481¹⁰¹

= 481^64+32+4+1

= 481⁶⁴⋅481³²⋅481⁴⋅481¹

≡ 318 ⋅ 226 ⋅ 598 ⋅ 481 mod 619
≡ 71868 ⋅ 598 ⋅ 481 mod 619 ≡ 64 ⋅ 598 ⋅ 481 mod 619
≡ 38272 ⋅ 481 mod 619 ≡ 513 ⋅ 481 mod 619
≡ 246753 mod 619 ≡ 391 mod 619

Es gilt also: 481¹⁰¹ ≡ 391 mod 619

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

=>89	= 1⋅80 + 9
=>80	= 8⋅9 + 8
=>9	= 1⋅8 + 1
=>8	= 8⋅1 + 0

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

Es gilt also: ggt(89,80)=1 = 9⋅89 -10⋅80

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

1 -9⋅89 = -10⋅80

-10⋅80 = -9⋅89 + 1 |+89⋅80

-10⋅80 + 89⋅80 = -9⋅89 + 89⋅80 + 1

(-10 + 89) ⋅ 80 = (-9 + 80) ⋅ 89 + 1

79⋅80 = 71⋅89 + 1

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

Somit 79⋅80 = 1 mod 89

79 ist also das Inverse von 80 mod 89