Um längere Rechnungen zu vermeiden, rechnen wir:

(4001 + 801) mod 4 ≡ (4001 mod 4 + 801 mod 4) mod 4.

4001 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 4001 = 4000+1 = 4 ⋅ 1000 +1.

801 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 801 = 800+1 = 4 ⋅ 200 +1.

Somit gilt:

(4001 + 801) mod 4 ≡ (1 + 1) mod 4 ≡ 2 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(70 ⋅ 61) mod 8 ≡ (70 mod 8 ⋅ 61 mod 8) mod 8.

70 mod 8 ≡ 6 mod 8 kann man relativ leicht bestimmen, weil ja 70 = 64 + 6 = 8 ⋅ 8 + 6 ist.

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

Somit gilt:

(70 ⋅ 61) mod 8 ≡ (6 ⋅ 5) mod 8 ≡ 30 mod 8 ≡ 6 mod 8.

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

2: 373²=373¹⁺¹=373¹⋅373¹ ≡ 373⋅373=139129 ≡ 36 mod 379

4: 373⁴=373²⁺²=373²⋅373² ≡ 36⋅36=1296 ≡ 159 mod 379

8: 373⁸=373⁴⁺⁴=373⁴⋅373⁴ ≡ 159⋅159=25281 ≡ 267 mod 379

16: 373¹⁶=373⁸⁺⁸=373⁸⋅373⁸ ≡ 267⋅267=71289 ≡ 37 mod 379

32: 373³²=373¹⁶⁺¹⁶=373¹⁶⋅373¹⁶ ≡ 37⋅37=1369 ≡ 232 mod 379

64: 373⁶⁴=373³²⁺³²=373³²⋅373³² ≡ 232⋅232=53824 ≡ 6 mod 379

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

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

124 = 64+32+16+8+4

741¹²⁴

= 741^64+32+16+8+4

= 741⁶⁴⋅741³²⋅741¹⁶⋅741⁸⋅741⁴

≡ 182 ⋅ 497 ⋅ 573 ⋅ 563 ⋅ 537 mod 953
≡ 90454 ⋅ 573 ⋅ 563 ⋅ 537 mod 953 ≡ 872 ⋅ 573 ⋅ 563 ⋅ 537 mod 953
≡ 499656 ⋅ 563 ⋅ 537 mod 953 ≡ 284 ⋅ 563 ⋅ 537 mod 953
≡ 159892 ⋅ 537 mod 953 ≡ 741 ⋅ 537 mod 953
≡ 397917 mod 953 ≡ 516 mod 953

Es gilt also: 741¹²⁴ ≡ 516 mod 953

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

=>83	= 1⋅80 + 3
=>80	= 26⋅3 + 2
=>3	= 1⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(83,80)=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= 3-1⋅2
2= 80-26⋅3	eingesetzt in die Zeile drüber:	1	= 1⋅3 -1⋅(80 -26⋅ 3) = 1⋅3 -1⋅80 +26⋅ 3) = -1⋅80 +27⋅ 3 (=1)
3= 83-1⋅80	eingesetzt in die Zeile drüber:	1	= -1⋅80 +27⋅(83 -1⋅ 80) = -1⋅80 +27⋅83 -27⋅ 80) = 27⋅83 -28⋅ 80 (=1)

Es gilt also: ggt(83,80)=1 = 27⋅83 -28⋅80

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

1 -27⋅83 = -28⋅80

-28⋅80 = -27⋅83 + 1 |+83⋅80

-28⋅80 + 83⋅80 = -27⋅83 + 83⋅80 + 1

(-28 + 83) ⋅ 80 = (-27 + 80) ⋅ 83 + 1

55⋅80 = 53⋅83 + 1

Es gilt also: 55⋅80 = 53⋅83 +1

Somit 55⋅80 = 1 mod 83

55 ist also das Inverse von 80 mod 83