Um längere Rechnungen zu vermeiden, rechnen wir:

(1502 + 147) mod 3 ≡ (1502 mod 3 + 147 mod 3) mod 3.

1502 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 1502 = 1500+2 = 3 ⋅ 500 +2.

147 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 147 = 150-3 = 3 ⋅ 50 -3 = 3 ⋅ 50 - 3 + 0.

Somit gilt:

(1502 + 147) mod 3 ≡ (2 + 0) mod 3 ≡ 2 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(23 ⋅ 62) mod 5 ≡ (23 mod 5 ⋅ 62 mod 5) mod 5.

23 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 23 = 20 + 3 = 4 ⋅ 5 + 3 ist.

62 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 62 = 60 + 2 = 12 ⋅ 5 + 2 ist.

Somit gilt:

(23 ⋅ 62) mod 5 ≡ (3 ⋅ 2) mod 5 ≡ 6 mod 5 ≡ 1 mod 5.

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

2: 677²=677¹⁺¹=677¹⋅677¹ ≡ 677⋅677=458329 ≡ 344 mod 757

4: 677⁴=677²⁺²=677²⋅677² ≡ 344⋅344=118336 ≡ 244 mod 757

8: 677⁸=677⁴⁺⁴=677⁴⋅677⁴ ≡ 244⋅244=59536 ≡ 490 mod 757

16: 677¹⁶=677⁸⁺⁸=677⁸⋅677⁸ ≡ 490⋅490=240100 ≡ 131 mod 757

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

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

111 = 64+32+8+4+2+1

383¹¹¹

= 383^{64+32+8+4+2+1}

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

≡ 235 ⋅ 239 ⋅ 188 ⋅ 289 ⋅ 482 ⋅ 383 mod 499
≡ 56165 ⋅ 188 ⋅ 289 ⋅ 482 ⋅ 383 mod 499 ≡ 277 ⋅ 188 ⋅ 289 ⋅ 482 ⋅ 383 mod 499
≡ 52076 ⋅ 289 ⋅ 482 ⋅ 383 mod 499 ≡ 180 ⋅ 289 ⋅ 482 ⋅ 383 mod 499
≡ 52020 ⋅ 482 ⋅ 383 mod 499 ≡ 124 ⋅ 482 ⋅ 383 mod 499
≡ 59768 ⋅ 383 mod 499 ≡ 387 ⋅ 383 mod 499
≡ 148221 mod 499 ≡ 18 mod 499

Es gilt also: 383¹¹¹ ≡ 18 mod 499

Berechnung des größten gemeinsamen Teilers von 97 und 66

=>97	= 1⋅66 + 31
=>66	= 2⋅31 + 4
=>31	= 7⋅4 + 3
=>4	= 1⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(97,66)=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= 4-1⋅3
3= 31-7⋅4	eingesetzt in die Zeile drüber:	1	= 1⋅4 -1⋅(31 -7⋅ 4) = 1⋅4 -1⋅31 +7⋅ 4) = -1⋅31 +8⋅ 4 (=1)
4= 66-2⋅31	eingesetzt in die Zeile drüber:	1	= -1⋅31 +8⋅(66 -2⋅ 31) = -1⋅31 +8⋅66 -16⋅ 31) = 8⋅66 -17⋅ 31 (=1)
31= 97-1⋅66	eingesetzt in die Zeile drüber:	1	= 8⋅66 -17⋅(97 -1⋅ 66) = 8⋅66 -17⋅97 +17⋅ 66) = -17⋅97 +25⋅ 66 (=1)

Es gilt also: ggt(97,66)=1 = -17⋅97 +25⋅66

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

1 +17⋅97 = +25⋅66

Es gilt also: 25⋅66 = 17⋅97 +1

Somit 25⋅66 = 1 mod 97

25 ist also das Inverse von 66 mod 97