Um längere Rechnungen zu vermeiden, rechnen wir:

(792 - 152) mod 8 ≡ (792 mod 8 - 152 mod 8) mod 8.

792 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 792 = 800-8 = 8 ⋅ 100 -8 = 8 ⋅ 100 - 8 + 0.

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

Somit gilt:

(792 - 152) mod 8 ≡ (0 - 0) mod 8 ≡ 0 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(61 ⋅ 24) mod 5 ≡ (61 mod 5 ⋅ 24 mod 5) mod 5.

61 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 61 = 60 + 1 = 12 ⋅ 5 + 1 ist.

24 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 24 = 20 + 4 = 4 ⋅ 5 + 4 ist.

Somit gilt:

(61 ⋅ 24) mod 5 ≡ (1 ⋅ 4) mod 5 ≡ 4 mod 5.

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

2: 374²=374¹⁺¹=374¹⋅374¹ ≡ 374⋅374=139876 ≡ 252 mod 563

4: 374⁴=374²⁺²=374²⋅374² ≡ 252⋅252=63504 ≡ 448 mod 563

8: 374⁸=374⁴⁺⁴=374⁴⋅374⁴ ≡ 448⋅448=200704 ≡ 276 mod 563

16: 374¹⁶=374⁸⁺⁸=374⁸⋅374⁸ ≡ 276⋅276=76176 ≡ 171 mod 563

32: 374³²=374¹⁶⁺¹⁶=374¹⁶⋅374¹⁶ ≡ 171⋅171=29241 ≡ 528 mod 563

64: 374⁶⁴=374³²⁺³²=374³²⋅374³² ≡ 528⋅528=278784 ≡ 99 mod 563

128: 374¹²⁸=374⁶⁴⁺⁶⁴=374⁶⁴⋅374⁶⁴ ≡ 99⋅99=9801 ≡ 230 mod 563

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

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

227 = 128+64+32+2+1

269²²⁷

= 269^{128+64+32+2+1}

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

≡ 165 ⋅ 186 ⋅ 324 ⋅ 6 ⋅ 269 mod 499
≡ 30690 ⋅ 324 ⋅ 6 ⋅ 269 mod 499 ≡ 251 ⋅ 324 ⋅ 6 ⋅ 269 mod 499
≡ 81324 ⋅ 6 ⋅ 269 mod 499 ≡ 486 ⋅ 6 ⋅ 269 mod 499
≡ 2916 ⋅ 269 mod 499 ≡ 421 ⋅ 269 mod 499
≡ 113249 mod 499 ≡ 475 mod 499

Es gilt also: 269²²⁷ ≡ 475 mod 499

Berechnung des größten gemeinsamen Teilers von 61 und 29

=>61	= 2⋅29 + 3
=>29	= 9⋅3 + 2
=>3	= 1⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(61,29)=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= 29-9⋅3	eingesetzt in die Zeile drüber:	1	= 1⋅3 -1⋅(29 -9⋅ 3) = 1⋅3 -1⋅29 +9⋅ 3) = -1⋅29 +10⋅ 3 (=1)
3= 61-2⋅29	eingesetzt in die Zeile drüber:	1	= -1⋅29 +10⋅(61 -2⋅ 29) = -1⋅29 +10⋅61 -20⋅ 29) = 10⋅61 -21⋅ 29 (=1)

Es gilt also: ggt(61,29)=1 = 10⋅61 -21⋅29

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

1 -10⋅61 = -21⋅29

-21⋅29 = -10⋅61 + 1 |+61⋅29

-21⋅29 + 61⋅29 = -10⋅61 + 61⋅29 + 1

(-21 + 61) ⋅ 29 = (-10 + 29) ⋅ 61 + 1

40⋅29 = 19⋅61 + 1

Es gilt also: 40⋅29 = 19⋅61 +1

Somit 40⋅29 = 1 mod 61

40 ist also das Inverse von 29 mod 61