Um längere Rechnungen zu vermeiden, rechnen wir:

(2996 + 17994) mod 6 ≡ (2996 mod 6 + 17994 mod 6) mod 6.

2996 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 2996 = 3000-4 = 6 ⋅ 500 -4 = 6 ⋅ 500 - 6 + 2.

17994 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 17994 = 18000-6 = 6 ⋅ 3000 -6 = 6 ⋅ 3000 - 6 + 0.

Somit gilt:

(2996 + 17994) mod 6 ≡ (2 + 0) mod 6 ≡ 2 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(83 ⋅ 23) mod 10 ≡ (83 mod 10 ⋅ 23 mod 10) mod 10.

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

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

Somit gilt:

(83 ⋅ 23) mod 10 ≡ (3 ⋅ 3) mod 10 ≡ 9 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: 816¹=816

2: 816²=816¹⁺¹=816¹⋅816¹ ≡ 816⋅816=665856 ≡ 895 mod 991

4: 816⁴=816²⁺²=816²⋅816² ≡ 895⋅895=801025 ≡ 297 mod 991

8: 816⁸=816⁴⁺⁴=816⁴⋅816⁴ ≡ 297⋅297=88209 ≡ 10 mod 991

16: 816¹⁶=816⁸⁺⁸=816⁸⋅816⁸ ≡ 10⋅10=100 ≡ 100 mod 991

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

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

213 = 128+64+16+4+1

247²¹³

= 247^{128+64+16+4+1}

= 247¹²⁸⋅247⁶⁴⋅247¹⁶⋅247⁴⋅247¹

≡ 201 ⋅ 398 ⋅ 166 ⋅ 363 ⋅ 247 mod 563
≡ 79998 ⋅ 166 ⋅ 363 ⋅ 247 mod 563 ≡ 52 ⋅ 166 ⋅ 363 ⋅ 247 mod 563
≡ 8632 ⋅ 363 ⋅ 247 mod 563 ≡ 187 ⋅ 363 ⋅ 247 mod 563
≡ 67881 ⋅ 247 mod 563 ≡ 321 ⋅ 247 mod 563
≡ 79287 mod 563 ≡ 467 mod 563

Es gilt also: 247²¹³ ≡ 467 mod 563

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

=>101	= 1⋅59 + 42
=>59	= 1⋅42 + 17
=>42	= 2⋅17 + 8
=>17	= 2⋅8 + 1
=>8	= 8⋅1 + 0

also gilt: ggt(101,59)=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= 17-2⋅8
8= 42-2⋅17	eingesetzt in die Zeile drüber:	1	= 1⋅17 -2⋅(42 -2⋅ 17) = 1⋅17 -2⋅42 +4⋅ 17) = -2⋅42 +5⋅ 17 (=1)
17= 59-1⋅42	eingesetzt in die Zeile drüber:	1	= -2⋅42 +5⋅(59 -1⋅ 42) = -2⋅42 +5⋅59 -5⋅ 42) = 5⋅59 -7⋅ 42 (=1)
42= 101-1⋅59	eingesetzt in die Zeile drüber:	1	= 5⋅59 -7⋅(101 -1⋅ 59) = 5⋅59 -7⋅101 +7⋅ 59) = -7⋅101 +12⋅ 59 (=1)

Es gilt also: ggt(101,59)=1 = -7⋅101 +12⋅59

oder wenn man -7⋅101 auf die linke Seite bringt:

1 +7⋅101 = +12⋅59

Es gilt also: 12⋅59 = 7⋅101 +1

Somit 12⋅59 = 1 mod 101

12 ist also das Inverse von 59 mod 101