Um längere Rechnungen zu vermeiden, rechnen wir:

(504 - 24997) mod 5 ≡ (504 mod 5 - 24997 mod 5) mod 5.

504 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 504 = 500+4 = 5 ⋅ 100 +4.

24997 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 24997 = 24000+997 = 5 ⋅ 4800 +997.

Somit gilt:

(504 - 24997) mod 5 ≡ (4 - 2) mod 5 ≡ 2 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(63 ⋅ 100) mod 3 ≡ (63 mod 3 ⋅ 100 mod 3) mod 3.

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

100 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 100 = 99 + 1 = 33 ⋅ 3 + 1 ist.

Somit gilt:

(63 ⋅ 100) mod 3 ≡ (0 ⋅ 1) mod 3 ≡ 0 mod 3.

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

2: 573²=573¹⁺¹=573¹⋅573¹ ≡ 573⋅573=328329 ≡ 861 mod 941

4: 573⁴=573²⁺²=573²⋅573² ≡ 861⋅861=741321 ≡ 754 mod 941

8: 573⁸=573⁴⁺⁴=573⁴⋅573⁴ ≡ 754⋅754=568516 ≡ 152 mod 941

16: 573¹⁶=573⁸⁺⁸=573⁸⋅573⁸ ≡ 152⋅152=23104 ≡ 520 mod 941

32: 573³²=573¹⁶⁺¹⁶=573¹⁶⋅573¹⁶ ≡ 520⋅520=270400 ≡ 333 mod 941

64: 573⁶⁴=573³²⁺³²=573³²⋅573³² ≡ 333⋅333=110889 ≡ 792 mod 941

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

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

156 = 128+16+8+4

392¹⁵⁶

= 392^128+16+8+4

= 392¹²⁸⋅392¹⁶⋅392⁸⋅392⁴

≡ 81 ⋅ 364 ⋅ 272 ⋅ 85 mod 409
≡ 29484 ⋅ 272 ⋅ 85 mod 409 ≡ 36 ⋅ 272 ⋅ 85 mod 409
≡ 9792 ⋅ 85 mod 409 ≡ 385 ⋅ 85 mod 409
≡ 32725 mod 409 ≡ 5 mod 409

Es gilt also: 392¹⁵⁶ ≡ 5 mod 409

Berechnung des größten gemeinsamen Teilers von 89 und 72

=>89	= 1⋅72 + 17
=>72	= 4⋅17 + 4
=>17	= 4⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(89,72)=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= 17-4⋅4
4= 72-4⋅17	eingesetzt in die Zeile drüber:	1	= 1⋅17 -4⋅(72 -4⋅ 17) = 1⋅17 -4⋅72 +16⋅ 17) = -4⋅72 +17⋅ 17 (=1)
17= 89-1⋅72	eingesetzt in die Zeile drüber:	1	= -4⋅72 +17⋅(89 -1⋅ 72) = -4⋅72 +17⋅89 -17⋅ 72) = 17⋅89 -21⋅ 72 (=1)

Es gilt also: ggt(89,72)=1 = 17⋅89 -21⋅72

oder wenn man 17⋅89 auf die linke Seite bringt:

1 -17⋅89 = -21⋅72

-21⋅72 = -17⋅89 + 1 |+89⋅72

-21⋅72 + 89⋅72 = -17⋅89 + 89⋅72 + 1

(-21 + 89) ⋅ 72 = (-17 + 72) ⋅ 89 + 1

68⋅72 = 55⋅89 + 1

Es gilt also: 68⋅72 = 55⋅89 +1

Somit 68⋅72 = 1 mod 89

68 ist also das Inverse von 72 mod 89