Um längere Rechnungen zu vermeiden, rechnen wir:

(9995 - 1501) mod 5 ≡ (9995 mod 5 - 1501 mod 5) mod 5.

9995 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 9995 = 9000+995 = 5 ⋅ 1800 +995.

1501 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 1501 = 1500+1 = 5 ⋅ 300 +1.

Somit gilt:

(9995 - 1501) mod 5 ≡ (0 - 1) mod 5 ≡ -1 mod 5 ≡ 4 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(19 ⋅ 87) mod 6 ≡ (19 mod 6 ⋅ 87 mod 6) mod 6.

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

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

Somit gilt:

(19 ⋅ 87) mod 6 ≡ (1 ⋅ 3) mod 6 ≡ 3 mod 6.

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

2: 505²=505¹⁺¹=505¹⋅505¹ ≡ 505⋅505=255025 ≡ 359 mod 571

4: 505⁴=505²⁺²=505²⋅505² ≡ 359⋅359=128881 ≡ 406 mod 571

8: 505⁸=505⁴⁺⁴=505⁴⋅505⁴ ≡ 406⋅406=164836 ≡ 388 mod 571

16: 505¹⁶=505⁸⁺⁸=505⁸⋅505⁸ ≡ 388⋅388=150544 ≡ 371 mod 571

32: 505³²=505¹⁶⁺¹⁶=505¹⁶⋅505¹⁶ ≡ 371⋅371=137641 ≡ 30 mod 571

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

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

252 = 128+64+32+16+8+4

246²⁵²

= 246^{128+64+32+16+8+4}

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

≡ 132 ⋅ 243 ⋅ 200 ⋅ 46 ⋅ 142 ⋅ 378 mod 479
≡ 32076 ⋅ 200 ⋅ 46 ⋅ 142 ⋅ 378 mod 479 ≡ 462 ⋅ 200 ⋅ 46 ⋅ 142 ⋅ 378 mod 479
≡ 92400 ⋅ 46 ⋅ 142 ⋅ 378 mod 479 ≡ 432 ⋅ 46 ⋅ 142 ⋅ 378 mod 479
≡ 19872 ⋅ 142 ⋅ 378 mod 479 ≡ 233 ⋅ 142 ⋅ 378 mod 479
≡ 33086 ⋅ 378 mod 479 ≡ 35 ⋅ 378 mod 479
≡ 13230 mod 479 ≡ 297 mod 479

Es gilt also: 246²⁵² ≡ 297 mod 479

Berechnung des größten gemeinsamen Teilers von 73 und 54

=>73	= 1⋅54 + 19
=>54	= 2⋅19 + 16
=>19	= 1⋅16 + 3
=>16	= 5⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(73,54)=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= 16-5⋅3
3= 19-1⋅16	eingesetzt in die Zeile drüber:	1	= 1⋅16 -5⋅(19 -1⋅ 16) = 1⋅16 -5⋅19 +5⋅ 16) = -5⋅19 +6⋅ 16 (=1)
16= 54-2⋅19	eingesetzt in die Zeile drüber:	1	= -5⋅19 +6⋅(54 -2⋅ 19) = -5⋅19 +6⋅54 -12⋅ 19) = 6⋅54 -17⋅ 19 (=1)
19= 73-1⋅54	eingesetzt in die Zeile drüber:	1	= 6⋅54 -17⋅(73 -1⋅ 54) = 6⋅54 -17⋅73 +17⋅ 54) = -17⋅73 +23⋅ 54 (=1)

Es gilt also: ggt(73,54)=1 = -17⋅73 +23⋅54

oder wenn man -17⋅73 auf die linke Seite bringt:

1 +17⋅73 = +23⋅54

Es gilt also: 23⋅54 = 17⋅73 +1

Somit 23⋅54 = 1 mod 73

23 ist also das Inverse von 54 mod 73