Um längere Rechnungen zu vermeiden, rechnen wir:

(3000 + 12002) mod 3 ≡ (3000 mod 3 + 12002 mod 3) mod 3.

3000 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 3000 = 3000+0 = 3 ⋅ 1000 +0.

12002 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 12002 = 12000+2 = 3 ⋅ 4000 +2.

Somit gilt:

(3000 + 12002) mod 3 ≡ (0 + 2) mod 3 ≡ 2 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(98 ⋅ 49) mod 10 ≡ (98 mod 10 ⋅ 49 mod 10) mod 10.

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

49 mod 10 ≡ 9 mod 10 kann man relativ leicht bestimmen, weil ja 49 = 40 + 9 = 4 ⋅ 10 + 9 ist.

Somit gilt:

(98 ⋅ 49) mod 10 ≡ (8 ⋅ 9) mod 10 ≡ 72 mod 10 ≡ 2 mod 10.

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

2: 439²=439¹⁺¹=439¹⋅439¹ ≡ 439⋅439=192721 ≡ 185 mod 587

4: 439⁴=439²⁺²=439²⋅439² ≡ 185⋅185=34225 ≡ 179 mod 587

8: 439⁸=439⁴⁺⁴=439⁴⋅439⁴ ≡ 179⋅179=32041 ≡ 343 mod 587

16: 439¹⁶=439⁸⁺⁸=439⁸⋅439⁸ ≡ 343⋅343=117649 ≡ 249 mod 587

32: 439³²=439¹⁶⁺¹⁶=439¹⁶⋅439¹⁶ ≡ 249⋅249=62001 ≡ 366 mod 587

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

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

188 = 128+32+16+8+4

283¹⁸⁸

= 283^{128+32+16+8+4}

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

≡ 43 ⋅ 186 ⋅ 385 ⋅ 151 ⋅ 119 mod 467
≡ 7998 ⋅ 385 ⋅ 151 ⋅ 119 mod 467 ≡ 59 ⋅ 385 ⋅ 151 ⋅ 119 mod 467
≡ 22715 ⋅ 151 ⋅ 119 mod 467 ≡ 299 ⋅ 151 ⋅ 119 mod 467
≡ 45149 ⋅ 119 mod 467 ≡ 317 ⋅ 119 mod 467
≡ 37723 mod 467 ≡ 363 mod 467

Es gilt also: 283¹⁸⁸ ≡ 363 mod 467

Berechnung des größten gemeinsamen Teilers von 61 und 52

=>61	= 1⋅52 + 9
=>52	= 5⋅9 + 7
=>9	= 1⋅7 + 2
=>7	= 3⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(61,52)=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= 7-3⋅2
2= 9-1⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -3⋅(9 -1⋅ 7) = 1⋅7 -3⋅9 +3⋅ 7) = -3⋅9 +4⋅ 7 (=1)
7= 52-5⋅9	eingesetzt in die Zeile drüber:	1	= -3⋅9 +4⋅(52 -5⋅ 9) = -3⋅9 +4⋅52 -20⋅ 9) = 4⋅52 -23⋅ 9 (=1)
9= 61-1⋅52	eingesetzt in die Zeile drüber:	1	= 4⋅52 -23⋅(61 -1⋅ 52) = 4⋅52 -23⋅61 +23⋅ 52) = -23⋅61 +27⋅ 52 (=1)

Es gilt also: ggt(61,52)=1 = -23⋅61 +27⋅52

oder wenn man -23⋅61 auf die linke Seite bringt:

1 +23⋅61 = +27⋅52

Es gilt also: 27⋅52 = 23⋅61 +1

Somit 27⋅52 = 1 mod 61

27 ist also das Inverse von 52 mod 61