Um längere Rechnungen zu vermeiden, rechnen wir:

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

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

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

Somit gilt:

(11998 + 1502) mod 3 ≡ (1 + 2) mod 3 ≡ 3 mod 3 ≡ 0 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(32 ⋅ 60) mod 10 ≡ (32 mod 10 ⋅ 60 mod 10) mod 10.

32 mod 10 ≡ 2 mod 10 kann man relativ leicht bestimmen, weil ja 32 = 30 + 2 = 3 ⋅ 10 + 2 ist.

60 mod 10 ≡ 0 mod 10 kann man relativ leicht bestimmen, weil ja 60 = 60 + 0 = 6 ⋅ 10 + 0 ist.

Somit gilt:

(32 ⋅ 60) mod 10 ≡ (2 ⋅ 0) mod 10 ≡ 0 mod 10.

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

2: 313²=313¹⁺¹=313¹⋅313¹ ≡ 313⋅313=97969 ≡ 241 mod 509

4: 313⁴=313²⁺²=313²⋅313² ≡ 241⋅241=58081 ≡ 55 mod 509

8: 313⁸=313⁴⁺⁴=313⁴⋅313⁴ ≡ 55⋅55=3025 ≡ 480 mod 509

16: 313¹⁶=313⁸⁺⁸=313⁸⋅313⁸ ≡ 480⋅480=230400 ≡ 332 mod 509

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

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

123 = 64+32+16+8+2+1

242¹²³

= 242^{64+32+16+8+2+1}

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

≡ 386 ⋅ 308 ⋅ 397 ⋅ 408 ⋅ 124 ⋅ 242 mod 487
≡ 118888 ⋅ 397 ⋅ 408 ⋅ 124 ⋅ 242 mod 487 ≡ 60 ⋅ 397 ⋅ 408 ⋅ 124 ⋅ 242 mod 487
≡ 23820 ⋅ 408 ⋅ 124 ⋅ 242 mod 487 ≡ 444 ⋅ 408 ⋅ 124 ⋅ 242 mod 487
≡ 181152 ⋅ 124 ⋅ 242 mod 487 ≡ 475 ⋅ 124 ⋅ 242 mod 487
≡ 58900 ⋅ 242 mod 487 ≡ 460 ⋅ 242 mod 487
≡ 111320 mod 487 ≡ 284 mod 487

Es gilt also: 242¹²³ ≡ 284 mod 487

Berechnung des größten gemeinsamen Teilers von 83 und 30

=>83	= 2⋅30 + 23
=>30	= 1⋅23 + 7
=>23	= 3⋅7 + 2
=>7	= 3⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(83,30)=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= 23-3⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -3⋅(23 -3⋅ 7) = 1⋅7 -3⋅23 +9⋅ 7) = -3⋅23 +10⋅ 7 (=1)
7= 30-1⋅23	eingesetzt in die Zeile drüber:	1	= -3⋅23 +10⋅(30 -1⋅ 23) = -3⋅23 +10⋅30 -10⋅ 23) = 10⋅30 -13⋅ 23 (=1)
23= 83-2⋅30	eingesetzt in die Zeile drüber:	1	= 10⋅30 -13⋅(83 -2⋅ 30) = 10⋅30 -13⋅83 +26⋅ 30) = -13⋅83 +36⋅ 30 (=1)

Es gilt also: ggt(83,30)=1 = -13⋅83 +36⋅30

oder wenn man -13⋅83 auf die linke Seite bringt:

1 +13⋅83 = +36⋅30

Es gilt also: 36⋅30 = 13⋅83 +1

Somit 36⋅30 = 1 mod 83

36 ist also das Inverse von 30 mod 83