Um längere Rechnungen zu vermeiden, rechnen wir:

(15001 - 15001) mod 3 ≡ (15001 mod 3 - 15001 mod 3) mod 3.

15001 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 15001 = 15000+1 = 3 ⋅ 5000 +1.

15001 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 15001 = 15000+1 = 3 ⋅ 5000 +1.

Somit gilt:

(15001 - 15001) mod 3 ≡ (1 - 1) mod 3 ≡ 0 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(93 ⋅ 15) mod 9 ≡ (93 mod 9 ⋅ 15 mod 9) mod 9.

93 mod 9 ≡ 3 mod 9 kann man relativ leicht bestimmen, weil ja 93 = 90 + 3 = 10 ⋅ 9 + 3 ist.

15 mod 9 ≡ 6 mod 9 kann man relativ leicht bestimmen, weil ja 15 = 9 + 6 = 1 ⋅ 9 + 6 ist.

Somit gilt:

(93 ⋅ 15) mod 9 ≡ (3 ⋅ 6) mod 9 ≡ 18 mod 9 ≡ 0 mod 9.

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

2: 531²=531¹⁺¹=531¹⋅531¹ ≡ 531⋅531=281961 ≡ 316 mod 619

4: 531⁴=531²⁺²=531²⋅531² ≡ 316⋅316=99856 ≡ 197 mod 619

8: 531⁸=531⁴⁺⁴=531⁴⋅531⁴ ≡ 197⋅197=38809 ≡ 431 mod 619

16: 531¹⁶=531⁸⁺⁸=531⁸⋅531⁸ ≡ 431⋅431=185761 ≡ 61 mod 619

32: 531³²=531¹⁶⁺¹⁶=531¹⁶⋅531¹⁶ ≡ 61⋅61=3721 ≡ 7 mod 619

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

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

219 = 128+64+16+8+2+1

350²¹⁹

= 350^{128+64+16+8+2+1}

= 350¹²⁸⋅350⁶⁴⋅350¹⁶⋅350⁸⋅350²⋅350¹

≡ 376 ⋅ 544 ⋅ 320 ⋅ 705 ⋅ 171 ⋅ 350 mod 821
≡ 204544 ⋅ 320 ⋅ 705 ⋅ 171 ⋅ 350 mod 821 ≡ 115 ⋅ 320 ⋅ 705 ⋅ 171 ⋅ 350 mod 821
≡ 36800 ⋅ 705 ⋅ 171 ⋅ 350 mod 821 ≡ 676 ⋅ 705 ⋅ 171 ⋅ 350 mod 821
≡ 476580 ⋅ 171 ⋅ 350 mod 821 ≡ 400 ⋅ 171 ⋅ 350 mod 821
≡ 68400 ⋅ 350 mod 821 ≡ 257 ⋅ 350 mod 821
≡ 89950 mod 821 ≡ 461 mod 821

Es gilt also: 350²¹⁹ ≡ 461 mod 821

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

=>59	= 1⋅54 + 5
=>54	= 10⋅5 + 4
=>5	= 1⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(59,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= 5-1⋅4
4= 54-10⋅5	eingesetzt in die Zeile drüber:	1	= 1⋅5 -1⋅(54 -10⋅ 5) = 1⋅5 -1⋅54 +10⋅ 5) = -1⋅54 +11⋅ 5 (=1)
5= 59-1⋅54	eingesetzt in die Zeile drüber:	1	= -1⋅54 +11⋅(59 -1⋅ 54) = -1⋅54 +11⋅59 -11⋅ 54) = 11⋅59 -12⋅ 54 (=1)

Es gilt also: ggt(59,54)=1 = 11⋅59 -12⋅54

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

1 -11⋅59 = -12⋅54

-12⋅54 = -11⋅59 + 1 |+59⋅54

-12⋅54 + 59⋅54 = -11⋅59 + 59⋅54 + 1

(-12 + 59) ⋅ 54 = (-11 + 54) ⋅ 59 + 1

47⋅54 = 43⋅59 + 1

Es gilt also: 47⋅54 = 43⋅59 +1

Somit 47⋅54 = 1 mod 59

47 ist also das Inverse von 54 mod 59