Um längere Rechnungen zu vermeiden, rechnen wir:

(117 + 118) mod 3 ≡ (117 mod 3 + 118 mod 3) mod 3.

117 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 117 = 120-3 = 3 ⋅ 40 -3 = 3 ⋅ 40 - 3 + 0.

118 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 118 = 120-2 = 3 ⋅ 40 -2 = 3 ⋅ 40 - 3 + 1.

Somit gilt:

(117 + 118) mod 3 ≡ (0 + 1) mod 3 ≡ 1 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(21 ⋅ 18) mod 6 ≡ (21 mod 6 ⋅ 18 mod 6) mod 6.

21 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 21 = 18 + 3 = 3 ⋅ 6 + 3 ist.

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

Somit gilt:

(21 ⋅ 18) mod 6 ≡ (3 ⋅ 0) mod 6 ≡ 0 mod 6.

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

2: 282²=282¹⁺¹=282¹⋅282¹ ≡ 282⋅282=79524 ≡ 285 mod 433

4: 282⁴=282²⁺²=282²⋅282² ≡ 285⋅285=81225 ≡ 254 mod 433

8: 282⁸=282⁴⁺⁴=282⁴⋅282⁴ ≡ 254⋅254=64516 ≡ 432 mod 433

16: 282¹⁶=282⁸⁺⁸=282⁸⋅282⁸ ≡ 432⋅432=186624 ≡ 1 mod 433

32: 282³²=282¹⁶⁺¹⁶=282¹⁶⋅282¹⁶ ≡ 1⋅1=1 ≡ 1 mod 433

64: 282⁶⁴=282³²⁺³²=282³²⋅282³² ≡ 1⋅1=1 ≡ 1 mod 433

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

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

151 = 128+16+4+2+1

695¹⁵¹

= 695^128+16+4+2+1

= 695¹²⁸⋅695¹⁶⋅695⁴⋅695²⋅695¹

≡ 361 ⋅ 844 ⋅ 576 ⋅ 24 ⋅ 695 mod 883
≡ 304684 ⋅ 576 ⋅ 24 ⋅ 695 mod 883 ≡ 49 ⋅ 576 ⋅ 24 ⋅ 695 mod 883
≡ 28224 ⋅ 24 ⋅ 695 mod 883 ≡ 851 ⋅ 24 ⋅ 695 mod 883
≡ 20424 ⋅ 695 mod 883 ≡ 115 ⋅ 695 mod 883
≡ 79925 mod 883 ≡ 455 mod 883

Es gilt also: 695¹⁵¹ ≡ 455 mod 883

Berechnung des größten gemeinsamen Teilers von 53 und 47

=>53	= 1⋅47 + 6
=>47	= 7⋅6 + 5
=>6	= 1⋅5 + 1
=>5	= 5⋅1 + 0

also gilt: ggt(53,47)=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= 6-1⋅5
5= 47-7⋅6	eingesetzt in die Zeile drüber:	1	= 1⋅6 -1⋅(47 -7⋅ 6) = 1⋅6 -1⋅47 +7⋅ 6) = -1⋅47 +8⋅ 6 (=1)
6= 53-1⋅47	eingesetzt in die Zeile drüber:	1	= -1⋅47 +8⋅(53 -1⋅ 47) = -1⋅47 +8⋅53 -8⋅ 47) = 8⋅53 -9⋅ 47 (=1)

Es gilt also: ggt(53,47)=1 = 8⋅53 -9⋅47

oder wenn man 8⋅53 auf die linke Seite bringt:

1 -8⋅53 = -9⋅47

-9⋅47 = -8⋅53 + 1 |+53⋅47

-9⋅47 + 53⋅47 = -8⋅53 + 53⋅47 + 1

(-9 + 53) ⋅ 47 = (-8 + 47) ⋅ 53 + 1

44⋅47 = 39⋅53 + 1

Es gilt also: 44⋅47 = 39⋅53 +1

Somit 44⋅47 = 1 mod 53

44 ist also das Inverse von 47 mod 53