Um längere Rechnungen zu vermeiden, rechnen wir:

(34993 + 2805) mod 7 ≡ (34993 mod 7 + 2805 mod 7) mod 7.

34993 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 34993 = 35000-7 = 7 ⋅ 5000 -7 = 7 ⋅ 5000 - 7 + 0.

2805 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 2805 = 2800+5 = 7 ⋅ 400 +5.

Somit gilt:

(34993 + 2805) mod 7 ≡ (0 + 5) mod 7 ≡ 5 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(21 ⋅ 18) mod 7 ≡ (21 mod 7 ⋅ 18 mod 7) mod 7.

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

18 mod 7 ≡ 4 mod 7 kann man relativ leicht bestimmen, weil ja 18 = 14 + 4 = 2 ⋅ 7 + 4 ist.

Somit gilt:

(21 ⋅ 18) mod 7 ≡ (0 ⋅ 4) mod 7 ≡ 0 mod 7.

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

2: 219²=219¹⁺¹=219¹⋅219¹ ≡ 219⋅219=47961 ≡ 75 mod 347

4: 219⁴=219²⁺²=219²⋅219² ≡ 75⋅75=5625 ≡ 73 mod 347

8: 219⁸=219⁴⁺⁴=219⁴⋅219⁴ ≡ 73⋅73=5329 ≡ 124 mod 347

16: 219¹⁶=219⁸⁺⁸=219⁸⋅219⁸ ≡ 124⋅124=15376 ≡ 108 mod 347

32: 219³²=219¹⁶⁺¹⁶=219¹⁶⋅219¹⁶ ≡ 108⋅108=11664 ≡ 213 mod 347

64: 219⁶⁴=219³²⁺³²=219³²⋅219³² ≡ 213⋅213=45369 ≡ 259 mod 347

128: 219¹²⁸=219⁶⁴⁺⁶⁴=219⁶⁴⋅219⁶⁴ ≡ 259⋅259=67081 ≡ 110 mod 347

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

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

219 = 128+64+16+8+2+1

468²¹⁹

= 468^{128+64+16+8+2+1}

= 468¹²⁸⋅468⁶⁴⋅468¹⁶⋅468⁸⋅468²⋅468¹

≡ 818 ⋅ 337 ⋅ 532 ⋅ 319 ⋅ 106 ⋅ 468 mod 823
≡ 275666 ⋅ 532 ⋅ 319 ⋅ 106 ⋅ 468 mod 823 ≡ 784 ⋅ 532 ⋅ 319 ⋅ 106 ⋅ 468 mod 823
≡ 417088 ⋅ 319 ⋅ 106 ⋅ 468 mod 823 ≡ 650 ⋅ 319 ⋅ 106 ⋅ 468 mod 823
≡ 207350 ⋅ 106 ⋅ 468 mod 823 ≡ 777 ⋅ 106 ⋅ 468 mod 823
≡ 82362 ⋅ 468 mod 823 ≡ 62 ⋅ 468 mod 823
≡ 29016 mod 823 ≡ 211 mod 823

Es gilt also: 468²¹⁹ ≡ 211 mod 823

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

=>59	= 1⋅31 + 28
=>31	= 1⋅28 + 3
=>28	= 9⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(59,31)=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= 28-9⋅3
3= 31-1⋅28	eingesetzt in die Zeile drüber:	1	= 1⋅28 -9⋅(31 -1⋅ 28) = 1⋅28 -9⋅31 +9⋅ 28) = -9⋅31 +10⋅ 28 (=1)
28= 59-1⋅31	eingesetzt in die Zeile drüber:	1	= -9⋅31 +10⋅(59 -1⋅ 31) = -9⋅31 +10⋅59 -10⋅ 31) = 10⋅59 -19⋅ 31 (=1)

Es gilt also: ggt(59,31)=1 = 10⋅59 -19⋅31

oder wenn man 10⋅59 auf die linke Seite bringt:

1 -10⋅59 = -19⋅31

-19⋅31 = -10⋅59 + 1 |+59⋅31

-19⋅31 + 59⋅31 = -10⋅59 + 59⋅31 + 1

(-19 + 59) ⋅ 31 = (-10 + 31) ⋅ 59 + 1

40⋅31 = 21⋅59 + 1

Es gilt also: 40⋅31 = 21⋅59 +1

Somit 40⋅31 = 1 mod 59

40 ist also das Inverse von 31 mod 59