Um längere Rechnungen zu vermeiden, rechnen wir:

(276 + 286) mod 7 ≡ (276 mod 7 + 286 mod 7) mod 7.

276 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 276 = 280-4 = 7 ⋅ 40 -4 = 7 ⋅ 40 - 7 + 3.

286 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 286 = 280+6 = 7 ⋅ 40 +6.

Somit gilt:

(276 + 286) mod 7 ≡ (3 + 6) mod 7 ≡ 9 mod 7 ≡ 2 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(94 ⋅ 55) mod 10 ≡ (94 mod 10 ⋅ 55 mod 10) mod 10.

94 mod 10 ≡ 4 mod 10 kann man relativ leicht bestimmen, weil ja 94 = 90 + 4 = 9 ⋅ 10 + 4 ist.

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

Somit gilt:

(94 ⋅ 55) mod 10 ≡ (4 ⋅ 5) mod 10 ≡ 20 mod 10 ≡ 0 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: 625¹=625

2: 625²=625¹⁺¹=625¹⋅625¹ ≡ 625⋅625=390625 ≡ 256 mod 641

4: 625⁴=625²⁺²=625²⋅625² ≡ 256⋅256=65536 ≡ 154 mod 641

8: 625⁸=625⁴⁺⁴=625⁴⋅625⁴ ≡ 154⋅154=23716 ≡ 640 mod 641

16: 625¹⁶=625⁸⁺⁸=625⁸⋅625⁸ ≡ 640⋅640=409600 ≡ 1 mod 641

32: 625³²=625¹⁶⁺¹⁶=625¹⁶⋅625¹⁶ ≡ 1⋅1=1 ≡ 1 mod 641

64: 625⁶⁴=625³²⁺³²=625³²⋅625³² ≡ 1⋅1=1 ≡ 1 mod 641

128: 625¹²⁸=625⁶⁴⁺⁶⁴=625⁶⁴⋅625⁶⁴ ≡ 1⋅1=1 ≡ 1 mod 641

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

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

97 = 64+32+1

300⁹⁷

= 300^64+32+1

= 300⁶⁴⋅300³²⋅300¹

≡ 194 ⋅ 552 ⋅ 300 mod 823
≡ 107088 ⋅ 300 mod 823 ≡ 98 ⋅ 300 mod 823
≡ 29400 mod 823 ≡ 595 mod 823

Es gilt also: 300⁹⁷ ≡ 595 mod 823

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

=>89	= 1⋅60 + 29
=>60	= 2⋅29 + 2
=>29	= 14⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(89,60)=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= 29-14⋅2
2= 60-2⋅29	eingesetzt in die Zeile drüber:	1	= 1⋅29 -14⋅(60 -2⋅ 29) = 1⋅29 -14⋅60 +28⋅ 29) = -14⋅60 +29⋅ 29 (=1)
29= 89-1⋅60	eingesetzt in die Zeile drüber:	1	= -14⋅60 +29⋅(89 -1⋅ 60) = -14⋅60 +29⋅89 -29⋅ 60) = 29⋅89 -43⋅ 60 (=1)

Es gilt also: ggt(89,60)=1 = 29⋅89 -43⋅60

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

1 -29⋅89 = -43⋅60

-43⋅60 = -29⋅89 + 1 |+89⋅60

-43⋅60 + 89⋅60 = -29⋅89 + 89⋅60 + 1

(-43 + 89) ⋅ 60 = (-29 + 60) ⋅ 89 + 1

46⋅60 = 31⋅89 + 1

Es gilt also: 46⋅60 = 31⋅89 +1

Somit 46⋅60 = 1 mod 89

46 ist also das Inverse von 60 mod 89