Um längere Rechnungen zu vermeiden, rechnen wir:

(84 - 16001) mod 8 ≡ (84 mod 8 - 16001 mod 8) mod 8.

84 mod 8 ≡ 4 mod 8 kann man relativ leicht bestimmen, weil ja 84 = 80+4 = 8 ⋅ 10 +4.

16001 mod 8 ≡ 1 mod 8 kann man relativ leicht bestimmen, weil ja 16001 = 16000+1 = 8 ⋅ 2000 +1.

Somit gilt:

(84 - 16001) mod 8 ≡ (4 - 1) mod 8 ≡ 3 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(68 ⋅ 62) mod 3 ≡ (68 mod 3 ⋅ 62 mod 3) mod 3.

68 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 68 = 66 + 2 = 22 ⋅ 3 + 2 ist.

62 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 62 = 60 + 2 = 20 ⋅ 3 + 2 ist.

Somit gilt:

(68 ⋅ 62) mod 3 ≡ (2 ⋅ 2) mod 3 ≡ 4 mod 3 ≡ 1 mod 3.

Die 32 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: 323¹=323

2: 323²=323¹⁺¹=323¹⋅323¹ ≡ 323⋅323=104329 ≡ 493 mod 509

4: 323⁴=323²⁺²=323²⋅323² ≡ 493⋅493=243049 ≡ 256 mod 509

8: 323⁸=323⁴⁺⁴=323⁴⋅323⁴ ≡ 256⋅256=65536 ≡ 384 mod 509

16: 323¹⁶=323⁸⁺⁸=323⁸⋅323⁸ ≡ 384⋅384=147456 ≡ 355 mod 509

32: 323³²=323¹⁶⁺¹⁶=323¹⁶⋅323¹⁶ ≡ 355⋅355=126025 ≡ 302 mod 509

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

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

110 = 64+32+8+4+2

417¹¹⁰

= 417^64+32+8+4+2

= 417⁶⁴⋅417³²⋅417⁸⋅417⁴⋅417²

≡ 695 ⋅ 272 ⋅ 214 ⋅ 312 ⋅ 821 mod 883
≡ 189040 ⋅ 214 ⋅ 312 ⋅ 821 mod 883 ≡ 78 ⋅ 214 ⋅ 312 ⋅ 821 mod 883
≡ 16692 ⋅ 312 ⋅ 821 mod 883 ≡ 798 ⋅ 312 ⋅ 821 mod 883
≡ 248976 ⋅ 821 mod 883 ≡ 853 ⋅ 821 mod 883
≡ 700313 mod 883 ≡ 94 mod 883

Es gilt also: 417¹¹⁰ ≡ 94 mod 883

Berechnung des größten gemeinsamen Teilers von 83 und 57

=>83	= 1⋅57 + 26
=>57	= 2⋅26 + 5
=>26	= 5⋅5 + 1
=>5	= 5⋅1 + 0

also gilt: ggt(83,57)=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= 26-5⋅5
5= 57-2⋅26	eingesetzt in die Zeile drüber:	1	= 1⋅26 -5⋅(57 -2⋅ 26) = 1⋅26 -5⋅57 +10⋅ 26) = -5⋅57 +11⋅ 26 (=1)
26= 83-1⋅57	eingesetzt in die Zeile drüber:	1	= -5⋅57 +11⋅(83 -1⋅ 57) = -5⋅57 +11⋅83 -11⋅ 57) = 11⋅83 -16⋅ 57 (=1)

Es gilt also: ggt(83,57)=1 = 11⋅83 -16⋅57

oder wenn man 11⋅83 auf die linke Seite bringt:

1 -11⋅83 = -16⋅57

-16⋅57 = -11⋅83 + 1 |+83⋅57

-16⋅57 + 83⋅57 = -11⋅83 + 83⋅57 + 1

(-16 + 83) ⋅ 57 = (-11 + 57) ⋅ 83 + 1

67⋅57 = 46⋅83 + 1

Es gilt also: 67⋅57 = 46⋅83 +1

Somit 67⋅57 = 1 mod 83

67 ist also das Inverse von 57 mod 83