Um längere Rechnungen zu vermeiden, rechnen wir:

(25002 - 24995) mod 5 ≡ (25002 mod 5 - 24995 mod 5) mod 5.

25002 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 25002 = 25000+2 = 5 ⋅ 5000 +2.

24995 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 24995 = 24000+995 = 5 ⋅ 4800 +995.

Somit gilt:

(25002 - 24995) mod 5 ≡ (2 - 0) mod 5 ≡ 2 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(88 ⋅ 59) mod 6 ≡ (88 mod 6 ⋅ 59 mod 6) mod 6.

88 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 88 = 84 + 4 = 14 ⋅ 6 + 4 ist.

59 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 59 = 54 + 5 = 9 ⋅ 6 + 5 ist.

Somit gilt:

(88 ⋅ 59) mod 6 ≡ (4 ⋅ 5) mod 6 ≡ 20 mod 6 ≡ 2 mod 6.

Die 16 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: 509¹=509

2: 509²=509¹⁺¹=509¹⋅509¹ ≡ 509⋅509=259081 ≡ 418 mod 571

4: 509⁴=509²⁺²=509²⋅509² ≡ 418⋅418=174724 ≡ 569 mod 571

8: 509⁸=509⁴⁺⁴=509⁴⋅509⁴ ≡ 569⋅569=323761 ≡ 4 mod 571

16: 509¹⁶=509⁸⁺⁸=509⁸⋅509⁸ ≡ 4⋅4=16 ≡ 16 mod 571

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

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

119 = 64+32+16+4+2+1

452¹¹⁹

= 452^{64+32+16+4+2+1}

= 452⁶⁴⋅452³²⋅452¹⁶⋅452⁴⋅452²⋅452¹

≡ 284 ⋅ 386 ⋅ 123 ⋅ 498 ⋅ 466 ⋅ 452 mod 641
≡ 109624 ⋅ 123 ⋅ 498 ⋅ 466 ⋅ 452 mod 641 ≡ 13 ⋅ 123 ⋅ 498 ⋅ 466 ⋅ 452 mod 641
≡ 1599 ⋅ 498 ⋅ 466 ⋅ 452 mod 641 ≡ 317 ⋅ 498 ⋅ 466 ⋅ 452 mod 641
≡ 157866 ⋅ 466 ⋅ 452 mod 641 ≡ 180 ⋅ 466 ⋅ 452 mod 641
≡ 83880 ⋅ 452 mod 641 ≡ 550 ⋅ 452 mod 641
≡ 248600 mod 641 ≡ 533 mod 641

Es gilt also: 452¹¹⁹ ≡ 533 mod 641

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

=>53	= 1⋅44 + 9
=>44	= 4⋅9 + 8
=>9	= 1⋅8 + 1
=>8	= 8⋅1 + 0

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

Es gilt also: ggt(53,44)=1 = 5⋅53 -6⋅44

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

1 -5⋅53 = -6⋅44

-6⋅44 = -5⋅53 + 1 |+53⋅44

-6⋅44 + 53⋅44 = -5⋅53 + 53⋅44 + 1

(-6 + 53) ⋅ 44 = (-5 + 44) ⋅ 53 + 1

47⋅44 = 39⋅53 + 1

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

Somit 47⋅44 = 1 mod 53

47 ist also das Inverse von 44 mod 53