Um längere Rechnungen zu vermeiden, rechnen wir:

(156 + 3199) mod 8 ≡ (156 mod 8 + 3199 mod 8) mod 8.

156 mod 8 ≡ 4 mod 8 kann man relativ leicht bestimmen, weil ja 156 = 160-4 = 8 ⋅ 20 -4 = 8 ⋅ 20 - 8 + 4.

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

Somit gilt:

(156 + 3199) mod 8 ≡ (4 + 7) mod 8 ≡ 11 mod 8 ≡ 3 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(47 ⋅ 65) mod 7 ≡ (47 mod 7 ⋅ 65 mod 7) mod 7.

47 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 47 = 42 + 5 = 6 ⋅ 7 + 5 ist.

65 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 65 = 63 + 2 = 9 ⋅ 7 + 2 ist.

Somit gilt:

(47 ⋅ 65) mod 7 ≡ (5 ⋅ 2) mod 7 ≡ 10 mod 7 ≡ 3 mod 7.

Die 64 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: 671¹=671

2: 671²=671¹⁺¹=671¹⋅671¹ ≡ 671⋅671=450241 ≡ 400 mod 691

4: 671⁴=671²⁺²=671²⋅671² ≡ 400⋅400=160000 ≡ 379 mod 691

8: 671⁸=671⁴⁺⁴=671⁴⋅671⁴ ≡ 379⋅379=143641 ≡ 604 mod 691

16: 671¹⁶=671⁸⁺⁸=671⁸⋅671⁸ ≡ 604⋅604=364816 ≡ 659 mod 691

32: 671³²=671¹⁶⁺¹⁶=671¹⁶⋅671¹⁶ ≡ 659⋅659=434281 ≡ 333 mod 691

64: 671⁶⁴=671³²⁺³²=671³²⋅671³² ≡ 333⋅333=110889 ≡ 329 mod 691

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

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

241 = 128+64+32+16+1

249²⁴¹

= 249^{128+64+32+16+1}

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

≡ 579 ⋅ 169 ⋅ 13 ⋅ 514 ⋅ 249 mod 823
≡ 97851 ⋅ 13 ⋅ 514 ⋅ 249 mod 823 ≡ 737 ⋅ 13 ⋅ 514 ⋅ 249 mod 823
≡ 9581 ⋅ 514 ⋅ 249 mod 823 ≡ 528 ⋅ 514 ⋅ 249 mod 823
≡ 271392 ⋅ 249 mod 823 ≡ 625 ⋅ 249 mod 823
≡ 155625 mod 823 ≡ 78 mod 823

Es gilt also: 249²⁴¹ ≡ 78 mod 823

Berechnung des größten gemeinsamen Teilers von 73 und 26

=>73	= 2⋅26 + 21
=>26	= 1⋅21 + 5
=>21	= 4⋅5 + 1
=>5	= 5⋅1 + 0

also gilt: ggt(73,26)=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= 21-4⋅5
5= 26-1⋅21	eingesetzt in die Zeile drüber:	1	= 1⋅21 -4⋅(26 -1⋅ 21) = 1⋅21 -4⋅26 +4⋅ 21) = -4⋅26 +5⋅ 21 (=1)
21= 73-2⋅26	eingesetzt in die Zeile drüber:	1	= -4⋅26 +5⋅(73 -2⋅ 26) = -4⋅26 +5⋅73 -10⋅ 26) = 5⋅73 -14⋅ 26 (=1)

Es gilt also: ggt(73,26)=1 = 5⋅73 -14⋅26

oder wenn man 5⋅73 auf die linke Seite bringt:

1 -5⋅73 = -14⋅26

-14⋅26 = -5⋅73 + 1 |+73⋅26

-14⋅26 + 73⋅26 = -5⋅73 + 73⋅26 + 1

(-14 + 73) ⋅ 26 = (-5 + 26) ⋅ 73 + 1

59⋅26 = 21⋅73 + 1

Es gilt also: 59⋅26 = 21⋅73 +1

Somit 59⋅26 = 1 mod 73

59 ist also das Inverse von 26 mod 73