Um längere Rechnungen zu vermeiden, rechnen wir:

(5999 - 30001) mod 6 ≡ (5999 mod 6 - 30001 mod 6) mod 6.

5999 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 5999 = 6000-1 = 6 ⋅ 1000 -1 = 6 ⋅ 1000 - 6 + 5.

30001 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 30001 = 30000+1 = 6 ⋅ 5000 +1.

Somit gilt:

(5999 - 30001) mod 6 ≡ (5 - 1) mod 6 ≡ 4 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(61 ⋅ 60) mod 10 ≡ (61 mod 10 ⋅ 60 mod 10) mod 10.

61 mod 10 ≡ 1 mod 10 kann man relativ leicht bestimmen, weil ja 61 = 60 + 1 = 6 ⋅ 10 + 1 ist.

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

Somit gilt:

(61 ⋅ 60) mod 10 ≡ (1 ⋅ 0) 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: 127¹=127

2: 127²=127¹⁺¹=127¹⋅127¹ ≡ 127⋅127=16129 ≡ 140 mod 271

4: 127⁴=127²⁺²=127²⋅127² ≡ 140⋅140=19600 ≡ 88 mod 271

8: 127⁸=127⁴⁺⁴=127⁴⋅127⁴ ≡ 88⋅88=7744 ≡ 156 mod 271

16: 127¹⁶=127⁸⁺⁸=127⁸⋅127⁸ ≡ 156⋅156=24336 ≡ 217 mod 271

32: 127³²=127¹⁶⁺¹⁶=127¹⁶⋅127¹⁶ ≡ 217⋅217=47089 ≡ 206 mod 271

64: 127⁶⁴=127³²⁺³²=127³²⋅127³² ≡ 206⋅206=42436 ≡ 160 mod 271

128: 127¹²⁸=127⁶⁴⁺⁶⁴=127⁶⁴⋅127⁶⁴ ≡ 160⋅160=25600 ≡ 126 mod 271

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

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

138 = 128+8+2

565¹³⁸

= 565^128+8+2

= 565¹²⁸⋅565⁸⋅565²

≡ 451 ⋅ 527 ⋅ 479 mod 809
≡ 237677 ⋅ 479 mod 809 ≡ 640 ⋅ 479 mod 809
≡ 306560 mod 809 ≡ 758 mod 809

Es gilt also: 565¹³⁸ ≡ 758 mod 809

Berechnung des größten gemeinsamen Teilers von 71 und 48

=>71	= 1⋅48 + 23
=>48	= 2⋅23 + 2
=>23	= 11⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(71,48)=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= 23-11⋅2
2= 48-2⋅23	eingesetzt in die Zeile drüber:	1	= 1⋅23 -11⋅(48 -2⋅ 23) = 1⋅23 -11⋅48 +22⋅ 23) = -11⋅48 +23⋅ 23 (=1)
23= 71-1⋅48	eingesetzt in die Zeile drüber:	1	= -11⋅48 +23⋅(71 -1⋅ 48) = -11⋅48 +23⋅71 -23⋅ 48) = 23⋅71 -34⋅ 48 (=1)

Es gilt also: ggt(71,48)=1 = 23⋅71 -34⋅48

oder wenn man 23⋅71 auf die linke Seite bringt:

1 -23⋅71 = -34⋅48

-34⋅48 = -23⋅71 + 1 |+71⋅48

-34⋅48 + 71⋅48 = -23⋅71 + 71⋅48 + 1

(-34 + 71) ⋅ 48 = (-23 + 48) ⋅ 71 + 1

37⋅48 = 25⋅71 + 1

Es gilt also: 37⋅48 = 25⋅71 +1

Somit 37⋅48 = 1 mod 71

37 ist also das Inverse von 48 mod 71