Um längere Rechnungen zu vermeiden, rechnen wir:

(212 + 21002) mod 7 ≡ (212 mod 7 + 21002 mod 7) mod 7.

212 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 212 = 210+2 = 7 ⋅ 30 +2.

21002 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 21002 = 21000+2 = 7 ⋅ 3000 +2.

Somit gilt:

(212 + 21002) mod 7 ≡ (2 + 2) mod 7 ≡ 4 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(63 ⋅ 56) mod 8 ≡ (63 mod 8 ⋅ 56 mod 8) mod 8.

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

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

Somit gilt:

(63 ⋅ 56) mod 8 ≡ (7 ⋅ 0) mod 8 ≡ 0 mod 8.

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

2: 270²=270¹⁺¹=270¹⋅270¹ ≡ 270⋅270=72900 ≡ 333 mod 733

4: 270⁴=270²⁺²=270²⋅270² ≡ 333⋅333=110889 ≡ 206 mod 733

8: 270⁸=270⁴⁺⁴=270⁴⋅270⁴ ≡ 206⋅206=42436 ≡ 655 mod 733

16: 270¹⁶=270⁸⁺⁸=270⁸⋅270⁸ ≡ 655⋅655=429025 ≡ 220 mod 733

32: 270³²=270¹⁶⁺¹⁶=270¹⁶⋅270¹⁶ ≡ 220⋅220=48400 ≡ 22 mod 733

64: 270⁶⁴=270³²⁺³²=270³²⋅270³² ≡ 22⋅22=484 ≡ 484 mod 733

128: 270¹²⁸=270⁶⁴⁺⁶⁴=270⁶⁴⋅270⁶⁴ ≡ 484⋅484=234256 ≡ 429 mod 733

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

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

134 = 128+4+2

680¹³⁴

= 680^128+4+2

= 680¹²⁸⋅680⁴⋅680²

≡ 578 ⋅ 563 ⋅ 461 mod 809
≡ 325414 ⋅ 461 mod 809 ≡ 196 ⋅ 461 mod 809
≡ 90356 mod 809 ≡ 557 mod 809

Es gilt also: 680¹³⁴ ≡ 557 mod 809

Berechnung des größten gemeinsamen Teilers von 59 und 50

=>59	= 1⋅50 + 9
=>50	= 5⋅9 + 5
=>9	= 1⋅5 + 4
=>5	= 1⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(59,50)=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-1⋅4
4= 9-1⋅5	eingesetzt in die Zeile drüber:	1	= 1⋅5 -1⋅(9 -1⋅ 5) = 1⋅5 -1⋅9 +1⋅ 5) = -1⋅9 +2⋅ 5 (=1)
5= 50-5⋅9	eingesetzt in die Zeile drüber:	1	= -1⋅9 +2⋅(50 -5⋅ 9) = -1⋅9 +2⋅50 -10⋅ 9) = 2⋅50 -11⋅ 9 (=1)
9= 59-1⋅50	eingesetzt in die Zeile drüber:	1	= 2⋅50 -11⋅(59 -1⋅ 50) = 2⋅50 -11⋅59 +11⋅ 50) = -11⋅59 +13⋅ 50 (=1)

Es gilt also: ggt(59,50)=1 = -11⋅59 +13⋅50

oder wenn man -11⋅59 auf die linke Seite bringt:

1 +11⋅59 = +13⋅50

Es gilt also: 13⋅50 = 11⋅59 +1

Somit 13⋅50 = 1 mod 59

13 ist also das Inverse von 50 mod 59