Um längere Rechnungen zu vermeiden, rechnen wir:

(87 - 903) mod 3 ≡ (87 mod 3 - 903 mod 3) mod 3.

87 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 87 = 90-3 = 3 ⋅ 30 -3 = 3 ⋅ 30 - 3 + 0.

903 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 903 = 900+3 = 3 ⋅ 300 +3.

Somit gilt:

(87 - 903) mod 3 ≡ (0 - 0) mod 3 ≡ 0 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(83 ⋅ 99) mod 5 ≡ (83 mod 5 ⋅ 99 mod 5) mod 5.

83 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 83 = 80 + 3 = 16 ⋅ 5 + 3 ist.

99 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 99 = 95 + 4 = 19 ⋅ 5 + 4 ist.

Somit gilt:

(83 ⋅ 99) mod 5 ≡ (3 ⋅ 4) mod 5 ≡ 12 mod 5 ≡ 2 mod 5.

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

2: 501²=501¹⁺¹=501¹⋅501¹ ≡ 501⋅501=251001 ≡ 420 mod 827

4: 501⁴=501²⁺²=501²⋅501² ≡ 420⋅420=176400 ≡ 249 mod 827

8: 501⁸=501⁴⁺⁴=501⁴⋅501⁴ ≡ 249⋅249=62001 ≡ 803 mod 827

16: 501¹⁶=501⁸⁺⁸=501⁸⋅501⁸ ≡ 803⋅803=644809 ≡ 576 mod 827

32: 501³²=501¹⁶⁺¹⁶=501¹⁶⋅501¹⁶ ≡ 576⋅576=331776 ≡ 149 mod 827

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

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

185 = 128+32+16+8+1

344¹⁸⁵

= 344^{128+32+16+8+1}

= 344¹²⁸⋅344³²⋅344¹⁶⋅344⁸⋅344¹

≡ 48 ⋅ 175 ⋅ 202 ⋅ 210 ⋅ 344 mod 467
≡ 8400 ⋅ 202 ⋅ 210 ⋅ 344 mod 467 ≡ 461 ⋅ 202 ⋅ 210 ⋅ 344 mod 467
≡ 93122 ⋅ 210 ⋅ 344 mod 467 ≡ 189 ⋅ 210 ⋅ 344 mod 467
≡ 39690 ⋅ 344 mod 467 ≡ 462 ⋅ 344 mod 467
≡ 158928 mod 467 ≡ 148 mod 467

Es gilt also: 344¹⁸⁵ ≡ 148 mod 467

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

=>59	= 1⋅45 + 14
=>45	= 3⋅14 + 3
=>14	= 4⋅3 + 2
=>3	= 1⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(59,45)=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= 14-4⋅3	eingesetzt in die Zeile drüber:	1	= 1⋅3 -1⋅(14 -4⋅ 3) = 1⋅3 -1⋅14 +4⋅ 3) = -1⋅14 +5⋅ 3 (=1)
3= 45-3⋅14	eingesetzt in die Zeile drüber:	1	= -1⋅14 +5⋅(45 -3⋅ 14) = -1⋅14 +5⋅45 -15⋅ 14) = 5⋅45 -16⋅ 14 (=1)
14= 59-1⋅45	eingesetzt in die Zeile drüber:	1	= 5⋅45 -16⋅(59 -1⋅ 45) = 5⋅45 -16⋅59 +16⋅ 45) = -16⋅59 +21⋅ 45 (=1)

Es gilt also: ggt(59,45)=1 = -16⋅59 +21⋅45

oder wenn man -16⋅59 auf die linke Seite bringt:

1 +16⋅59 = +21⋅45

Es gilt also: 21⋅45 = 16⋅59 +1

Somit 21⋅45 = 1 mod 59

21 ist also das Inverse von 45 mod 59