Um längere Rechnungen zu vermeiden, rechnen wir:

(27998 + 203) mod 7 ≡ (27998 mod 7 + 203 mod 7) mod 7.

27998 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 27998 = 28000-2 = 7 ⋅ 4000 -2 = 7 ⋅ 4000 - 7 + 5.

203 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 203 = 210-7 = 7 ⋅ 30 -7 = 7 ⋅ 30 - 7 + 0.

Somit gilt:

(27998 + 203) mod 7 ≡ (5 + 0) mod 7 ≡ 5 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(21 ⋅ 51) mod 8 ≡ (21 mod 8 ⋅ 51 mod 8) mod 8.

21 mod 8 ≡ 5 mod 8 kann man relativ leicht bestimmen, weil ja 21 = 16 + 5 = 2 ⋅ 8 + 5 ist.

51 mod 8 ≡ 3 mod 8 kann man relativ leicht bestimmen, weil ja 51 = 48 + 3 = 6 ⋅ 8 + 3 ist.

Somit gilt:

(21 ⋅ 51) mod 8 ≡ (5 ⋅ 3) mod 8 ≡ 15 mod 8 ≡ 7 mod 8.

Die 32 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: 220¹=220

2: 220²=220¹⁺¹=220¹⋅220¹ ≡ 220⋅220=48400 ≡ 249 mod 269

4: 220⁴=220²⁺²=220²⋅220² ≡ 249⋅249=62001 ≡ 131 mod 269

8: 220⁸=220⁴⁺⁴=220⁴⋅220⁴ ≡ 131⋅131=17161 ≡ 214 mod 269

16: 220¹⁶=220⁸⁺⁸=220⁸⋅220⁸ ≡ 214⋅214=45796 ≡ 66 mod 269

32: 220³²=220¹⁶⁺¹⁶=220¹⁶⋅220¹⁶ ≡ 66⋅66=4356 ≡ 52 mod 269

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

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

191 = 128+32+16+8+4+2+1

516¹⁹¹

= 516^{128+32+16+8+4+2+1}

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

≡ 49 ⋅ 768 ⋅ 183 ⋅ 448 ⋅ 271 ⋅ 293 ⋅ 516 mod 839
≡ 37632 ⋅ 183 ⋅ 448 ⋅ 271 ⋅ 293 ⋅ 516 mod 839 ≡ 716 ⋅ 183 ⋅ 448 ⋅ 271 ⋅ 293 ⋅ 516 mod 839
≡ 131028 ⋅ 448 ⋅ 271 ⋅ 293 ⋅ 516 mod 839 ≡ 144 ⋅ 448 ⋅ 271 ⋅ 293 ⋅ 516 mod 839
≡ 64512 ⋅ 271 ⋅ 293 ⋅ 516 mod 839 ≡ 748 ⋅ 271 ⋅ 293 ⋅ 516 mod 839
≡ 202708 ⋅ 293 ⋅ 516 mod 839 ≡ 509 ⋅ 293 ⋅ 516 mod 839
≡ 149137 ⋅ 516 mod 839 ≡ 634 ⋅ 516 mod 839
≡ 327144 mod 839 ≡ 773 mod 839

Es gilt also: 516¹⁹¹ ≡ 773 mod 839

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