Um längere Rechnungen zu vermeiden, rechnen wir:

(3193 + 168) mod 8 ≡ (3193 mod 8 + 168 mod 8) mod 8.

3193 mod 8 ≡ 1 mod 8 kann man relativ leicht bestimmen, weil ja 3193 = 3200-7 = 8 ⋅ 400 -7 = 8 ⋅ 400 - 8 + 1.

168 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 168 = 160+8 = 8 ⋅ 20 +8.

Somit gilt:

(3193 + 168) mod 8 ≡ (1 + 0) mod 8 ≡ 1 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(44 ⋅ 27) mod 10 ≡ (44 mod 10 ⋅ 27 mod 10) mod 10.

44 mod 10 ≡ 4 mod 10 kann man relativ leicht bestimmen, weil ja 44 = 40 + 4 = 4 ⋅ 10 + 4 ist.

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

Somit gilt:

(44 ⋅ 27) mod 10 ≡ (4 ⋅ 7) mod 10 ≡ 28 mod 10 ≡ 8 mod 10.

Die 128 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: 343¹=343

2: 343²=343¹⁺¹=343¹⋅343¹ ≡ 343⋅343=117649 ≡ 283 mod 631

4: 343⁴=343²⁺²=343²⋅343² ≡ 283⋅283=80089 ≡ 583 mod 631

8: 343⁸=343⁴⁺⁴=343⁴⋅343⁴ ≡ 583⋅583=339889 ≡ 411 mod 631

16: 343¹⁶=343⁸⁺⁸=343⁸⋅343⁸ ≡ 411⋅411=168921 ≡ 444 mod 631

32: 343³²=343¹⁶⁺¹⁶=343¹⁶⋅343¹⁶ ≡ 444⋅444=197136 ≡ 264 mod 631

64: 343⁶⁴=343³²⁺³²=343³²⋅343³² ≡ 264⋅264=69696 ≡ 286 mod 631

128: 343¹²⁸=343⁶⁴⁺⁶⁴=343⁶⁴⋅343⁶⁴ ≡ 286⋅286=81796 ≡ 397 mod 631

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

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

99 = 64+32+2+1

277⁹⁹

= 277^64+32+2+1

= 277⁶⁴⋅277³²⋅277²⋅277¹

≡ 137 ⋅ 161 ⋅ 256 ⋅ 277 mod 293
≡ 22057 ⋅ 256 ⋅ 277 mod 293 ≡ 82 ⋅ 256 ⋅ 277 mod 293
≡ 20992 ⋅ 277 mod 293 ≡ 189 ⋅ 277 mod 293
≡ 52353 mod 293 ≡ 199 mod 293

Es gilt also: 277⁹⁹ ≡ 199 mod 293

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

=>79	= 1⋅41 + 38
=>41	= 1⋅38 + 3
=>38	= 12⋅3 + 2
=>3	= 1⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(79,41)=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= 3-1⋅2
2= 38-12⋅3	eingesetzt in die Zeile drüber:	1	= 1⋅3 -1⋅(38 -12⋅ 3) = 1⋅3 -1⋅38 +12⋅ 3) = -1⋅38 +13⋅ 3 (=1)
3= 41-1⋅38	eingesetzt in die Zeile drüber:	1	= -1⋅38 +13⋅(41 -1⋅ 38) = -1⋅38 +13⋅41 -13⋅ 38) = 13⋅41 -14⋅ 38 (=1)
38= 79-1⋅41	eingesetzt in die Zeile drüber:	1	= 13⋅41 -14⋅(79 -1⋅ 41) = 13⋅41 -14⋅79 +14⋅ 41) = -14⋅79 +27⋅ 41 (=1)

Es gilt also: ggt(79,41)=1 = -14⋅79 +27⋅41

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

1 +14⋅79 = +27⋅41

Es gilt also: 27⋅41 = 14⋅79 +1

Somit 27⋅41 = 1 mod 79

27 ist also das Inverse von 41 mod 79