Um längere Rechnungen zu vermeiden, rechnen wir:

(116 + 7998) mod 4 ≡ (116 mod 4 + 7998 mod 4) mod 4.

116 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 116 = 120-4 = 4 ⋅ 30 -4 = 4 ⋅ 30 - 4 + 0.

7998 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 7998 = 7000+998 = 4 ⋅ 1750 +998.

Somit gilt:

(116 + 7998) mod 4 ≡ (0 + 2) mod 4 ≡ 2 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(35 ⋅ 80) mod 7 ≡ (35 mod 7 ⋅ 80 mod 7) mod 7.

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

80 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 80 = 77 + 3 = 11 ⋅ 7 + 3 ist.

Somit gilt:

(35 ⋅ 80) mod 7 ≡ (0 ⋅ 3) mod 7 ≡ 0 mod 7.

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

2: 477²=477¹⁺¹=477¹⋅477¹ ≡ 477⋅477=227529 ≡ 145 mod 661

4: 477⁴=477²⁺²=477²⋅477² ≡ 145⋅145=21025 ≡ 534 mod 661

8: 477⁸=477⁴⁺⁴=477⁴⋅477⁴ ≡ 534⋅534=285156 ≡ 265 mod 661

16: 477¹⁶=477⁸⁺⁸=477⁸⋅477⁸ ≡ 265⋅265=70225 ≡ 159 mod 661

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

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

250 = 128+64+32+16+8+2

623²⁵⁰

= 623^{128+64+32+16+8+2}

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

≡ 188 ⋅ 310 ⋅ 64 ⋅ 8 ⋅ 188 ⋅ 64 mod 631
≡ 58280 ⋅ 64 ⋅ 8 ⋅ 188 ⋅ 64 mod 631 ≡ 228 ⋅ 64 ⋅ 8 ⋅ 188 ⋅ 64 mod 631
≡ 14592 ⋅ 8 ⋅ 188 ⋅ 64 mod 631 ≡ 79 ⋅ 8 ⋅ 188 ⋅ 64 mod 631
≡ 632 ⋅ 188 ⋅ 64 mod 631 ≡ 1 ⋅ 188 ⋅ 64 mod 631
≡ 188 ⋅ 64 mod 631
≡ 12032 mod 631 ≡ 43 mod 631

Es gilt also: 623²⁵⁰ ≡ 43 mod 631

Berechnung des größten gemeinsamen Teilers von 79 und 56

=>79	= 1⋅56 + 23
=>56	= 2⋅23 + 10
=>23	= 2⋅10 + 3
=>10	= 3⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(79,56)=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= 10-3⋅3
3= 23-2⋅10	eingesetzt in die Zeile drüber:	1	= 1⋅10 -3⋅(23 -2⋅ 10) = 1⋅10 -3⋅23 +6⋅ 10) = -3⋅23 +7⋅ 10 (=1)
10= 56-2⋅23	eingesetzt in die Zeile drüber:	1	= -3⋅23 +7⋅(56 -2⋅ 23) = -3⋅23 +7⋅56 -14⋅ 23) = 7⋅56 -17⋅ 23 (=1)
23= 79-1⋅56	eingesetzt in die Zeile drüber:	1	= 7⋅56 -17⋅(79 -1⋅ 56) = 7⋅56 -17⋅79 +17⋅ 56) = -17⋅79 +24⋅ 56 (=1)

Es gilt also: ggt(79,56)=1 = -17⋅79 +24⋅56

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

1 +17⋅79 = +24⋅56

Es gilt also: 24⋅56 = 17⋅79 +1

Somit 24⋅56 = 1 mod 79

24 ist also das Inverse von 56 mod 79