Um längere Rechnungen zu vermeiden, rechnen wir:

(72 - 801) mod 8 ≡ (72 mod 8 - 801 mod 8) mod 8.

72 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 72 = 80-8 = 8 ⋅ 10 -8 = 8 ⋅ 10 - 8 + 0.

801 mod 8 ≡ 1 mod 8 kann man relativ leicht bestimmen, weil ja 801 = 800+1 = 8 ⋅ 100 +1.

Somit gilt:

(72 - 801) mod 8 ≡ (0 - 1) mod 8 ≡ -1 mod 8 ≡ 7 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(60 ⋅ 97) mod 8 ≡ (60 mod 8 ⋅ 97 mod 8) mod 8.

60 mod 8 ≡ 4 mod 8 kann man relativ leicht bestimmen, weil ja 60 = 56 + 4 = 7 ⋅ 8 + 4 ist.

97 mod 8 ≡ 1 mod 8 kann man relativ leicht bestimmen, weil ja 97 = 96 + 1 = 12 ⋅ 8 + 1 ist.

Somit gilt:

(60 ⋅ 97) mod 8 ≡ (4 ⋅ 1) mod 8 ≡ 4 mod 8.

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

2: 847²=847¹⁺¹=847¹⋅847¹ ≡ 847⋅847=717409 ≡ 879 mod 907

4: 847⁴=847²⁺²=847²⋅847² ≡ 879⋅879=772641 ≡ 784 mod 907

8: 847⁸=847⁴⁺⁴=847⁴⋅847⁴ ≡ 784⋅784=614656 ≡ 617 mod 907

16: 847¹⁶=847⁸⁺⁸=847⁸⋅847⁸ ≡ 617⋅617=380689 ≡ 656 mod 907

32: 847³²=847¹⁶⁺¹⁶=847¹⁶⋅847¹⁶ ≡ 656⋅656=430336 ≡ 418 mod 907

64: 847⁶⁴=847³²⁺³²=847³²⋅847³² ≡ 418⋅418=174724 ≡ 580 mod 907

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

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

201 = 128+64+8+1

206²⁰¹

= 206^128+64+8+1

= 206¹²⁸⋅206⁶⁴⋅206⁸⋅206¹

≡ 352 ⋅ 276 ⋅ 517 ⋅ 206 mod 677
≡ 97152 ⋅ 517 ⋅ 206 mod 677 ≡ 341 ⋅ 517 ⋅ 206 mod 677
≡ 176297 ⋅ 206 mod 677 ≡ 277 ⋅ 206 mod 677
≡ 57062 mod 677 ≡ 194 mod 677

Es gilt also: 206²⁰¹ ≡ 194 mod 677

Berechnung des größten gemeinsamen Teilers von 73 und 54

=>73	= 1⋅54 + 19
=>54	= 2⋅19 + 16
=>19	= 1⋅16 + 3
=>16	= 5⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(73,54)=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= 16-5⋅3
3= 19-1⋅16	eingesetzt in die Zeile drüber:	1	= 1⋅16 -5⋅(19 -1⋅ 16) = 1⋅16 -5⋅19 +5⋅ 16) = -5⋅19 +6⋅ 16 (=1)
16= 54-2⋅19	eingesetzt in die Zeile drüber:	1	= -5⋅19 +6⋅(54 -2⋅ 19) = -5⋅19 +6⋅54 -12⋅ 19) = 6⋅54 -17⋅ 19 (=1)
19= 73-1⋅54	eingesetzt in die Zeile drüber:	1	= 6⋅54 -17⋅(73 -1⋅ 54) = 6⋅54 -17⋅73 +17⋅ 54) = -17⋅73 +23⋅ 54 (=1)

Es gilt also: ggt(73,54)=1 = -17⋅73 +23⋅54

oder wenn man -17⋅73 auf die linke Seite bringt:

1 +17⋅73 = +23⋅54

Es gilt also: 23⋅54 = 17⋅73 +1

Somit 23⋅54 = 1 mod 73

23 ist also das Inverse von 54 mod 73