Um längere Rechnungen zu vermeiden, rechnen wir:

(2999 - 61) mod 3 ≡ (2999 mod 3 - 61 mod 3) mod 3.

2999 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 2999 = 3000-1 = 3 ⋅ 1000 -1 = 3 ⋅ 1000 - 3 + 2.

61 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 61 = 60+1 = 3 ⋅ 20 +1.

Somit gilt:

(2999 - 61) mod 3 ≡ (2 - 1) mod 3 ≡ 1 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(37 ⋅ 76) mod 7 ≡ (37 mod 7 ⋅ 76 mod 7) mod 7.

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

76 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 76 = 70 + 6 = 10 ⋅ 7 + 6 ist.

Somit gilt:

(37 ⋅ 76) mod 7 ≡ (2 ⋅ 6) mod 7 ≡ 12 mod 7 ≡ 5 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: 779¹=779

2: 779²=779¹⁺¹=779¹⋅779¹ ≡ 779⋅779=606841 ≡ 133 mod 887

4: 779⁴=779²⁺²=779²⋅779² ≡ 133⋅133=17689 ≡ 836 mod 887

8: 779⁸=779⁴⁺⁴=779⁴⋅779⁴ ≡ 836⋅836=698896 ≡ 827 mod 887

16: 779¹⁶=779⁸⁺⁸=779⁸⋅779⁸ ≡ 827⋅827=683929 ≡ 52 mod 887

32: 779³²=779¹⁶⁺¹⁶=779¹⁶⋅779¹⁶ ≡ 52⋅52=2704 ≡ 43 mod 887

64: 779⁶⁴=779³²⁺³²=779³²⋅779³² ≡ 43⋅43=1849 ≡ 75 mod 887

128: 779¹²⁸=779⁶⁴⁺⁶⁴=779⁶⁴⋅779⁶⁴ ≡ 75⋅75=5625 ≡ 303 mod 887

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

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

86 = 64+16+4+2

581⁸⁶

= 581^64+16+4+2

= 581⁶⁴⋅581¹⁶⋅581⁴⋅581²

≡ 794 ⋅ 330 ⋅ 163 ⋅ 185 mod 811
≡ 262020 ⋅ 163 ⋅ 185 mod 811 ≡ 67 ⋅ 163 ⋅ 185 mod 811
≡ 10921 ⋅ 185 mod 811 ≡ 378 ⋅ 185 mod 811
≡ 69930 mod 811 ≡ 184 mod 811

Es gilt also: 581⁸⁶ ≡ 184 mod 811

Berechnung des größten gemeinsamen Teilers von 67 und 62

=>67	= 1⋅62 + 5
=>62	= 12⋅5 + 2
=>5	= 2⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(67,62)=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= 5-2⋅2
2= 62-12⋅5	eingesetzt in die Zeile drüber:	1	= 1⋅5 -2⋅(62 -12⋅ 5) = 1⋅5 -2⋅62 +24⋅ 5) = -2⋅62 +25⋅ 5 (=1)
5= 67-1⋅62	eingesetzt in die Zeile drüber:	1	= -2⋅62 +25⋅(67 -1⋅ 62) = -2⋅62 +25⋅67 -25⋅ 62) = 25⋅67 -27⋅ 62 (=1)

Es gilt also: ggt(67,62)=1 = 25⋅67 -27⋅62

oder wenn man 25⋅67 auf die linke Seite bringt:

1 -25⋅67 = -27⋅62

-27⋅62 = -25⋅67 + 1 |+67⋅62

-27⋅62 + 67⋅62 = -25⋅67 + 67⋅62 + 1

(-27 + 67) ⋅ 62 = (-25 + 62) ⋅ 67 + 1

40⋅62 = 37⋅67 + 1

Es gilt also: 40⋅62 = 37⋅67 +1

Somit 40⋅62 = 1 mod 67

40 ist also das Inverse von 62 mod 67