Um längere Rechnungen zu vermeiden, rechnen wir:

(149 + 118) mod 3 ≡ (149 mod 3 + 118 mod 3) mod 3.

149 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 149 = 150-1 = 3 ⋅ 50 -1 = 3 ⋅ 50 - 3 + 2.

118 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 118 = 120-2 = 3 ⋅ 40 -2 = 3 ⋅ 40 - 3 + 1.

Somit gilt:

(149 + 118) mod 3 ≡ (2 + 1) mod 3 ≡ 3 mod 3 ≡ 0 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(66 ⋅ 38) mod 5 ≡ (66 mod 5 ⋅ 38 mod 5) mod 5.

66 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 66 = 65 + 1 = 13 ⋅ 5 + 1 ist.

38 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 38 = 35 + 3 = 7 ⋅ 5 + 3 ist.

Somit gilt:

(66 ⋅ 38) mod 5 ≡ (1 ⋅ 3) mod 5 ≡ 3 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: 460¹=460

2: 460²=460¹⁺¹=460¹⋅460¹ ≡ 460⋅460=211600 ≡ 395 mod 797

4: 460⁴=460²⁺²=460²⋅460² ≡ 395⋅395=156025 ≡ 610 mod 797

8: 460⁸=460⁴⁺⁴=460⁴⋅460⁴ ≡ 610⋅610=372100 ≡ 698 mod 797

16: 460¹⁶=460⁸⁺⁸=460⁸⋅460⁸ ≡ 698⋅698=487204 ≡ 237 mod 797

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

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

248 = 128+64+32+16+8

554²⁴⁸

= 554^{128+64+32+16+8}

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

≡ 587 ⋅ 86 ⋅ 516 ⋅ 520 ⋅ 124 mod 619
≡ 50482 ⋅ 516 ⋅ 520 ⋅ 124 mod 619 ≡ 343 ⋅ 516 ⋅ 520 ⋅ 124 mod 619
≡ 176988 ⋅ 520 ⋅ 124 mod 619 ≡ 573 ⋅ 520 ⋅ 124 mod 619
≡ 297960 ⋅ 124 mod 619 ≡ 221 ⋅ 124 mod 619
≡ 27404 mod 619 ≡ 168 mod 619

Es gilt also: 554²⁴⁸ ≡ 168 mod 619

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

=>101	= 1⋅89 + 12
=>89	= 7⋅12 + 5
=>12	= 2⋅5 + 2
=>5	= 2⋅2 + 1
=>2	= 2⋅1 + 0

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

Es gilt also: ggt(101,89)=1 = -37⋅101 +42⋅89

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

1 +37⋅101 = +42⋅89

Es gilt also: 42⋅89 = 37⋅101 +1

Somit 42⋅89 = 1 mod 101

42 ist also das Inverse von 89 mod 101