Um längere Rechnungen zu vermeiden, rechnen wir:

(2504 + 10001) mod 5 ≡ (2504 mod 5 + 10001 mod 5) mod 5.

2504 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 2504 = 2500+4 = 5 ⋅ 500 +4.

10001 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 10001 = 10000+1 = 5 ⋅ 2000 +1.

Somit gilt:

(2504 + 10001) mod 5 ≡ (4 + 1) mod 5 ≡ 5 mod 5 ≡ 0 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(43 ⋅ 28) mod 5 ≡ (43 mod 5 ⋅ 28 mod 5) mod 5.

43 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 43 = 40 + 3 = 8 ⋅ 5 + 3 ist.

28 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 28 = 25 + 3 = 5 ⋅ 5 + 3 ist.

Somit gilt:

(43 ⋅ 28) mod 5 ≡ (3 ⋅ 3) mod 5 ≡ 9 mod 5 ≡ 4 mod 5.

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

2: 246²=246¹⁺¹=246¹⋅246¹ ≡ 246⋅246=60516 ≡ 410 mod 733

4: 246⁴=246²⁺²=246²⋅246² ≡ 410⋅410=168100 ≡ 243 mod 733

8: 246⁸=246⁴⁺⁴=246⁴⋅246⁴ ≡ 243⋅243=59049 ≡ 409 mod 733

16: 246¹⁶=246⁸⁺⁸=246⁸⋅246⁸ ≡ 409⋅409=167281 ≡ 157 mod 733

32: 246³²=246¹⁶⁺¹⁶=246¹⁶⋅246¹⁶ ≡ 157⋅157=24649 ≡ 460 mod 733

64: 246⁶⁴=246³²⁺³²=246³²⋅246³² ≡ 460⋅460=211600 ≡ 496 mod 733

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

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

242 = 128+64+32+16+2

165²⁴²

= 165^{128+64+32+16+2}

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

≡ 9 ⋅ 208 ⋅ 182 ⋅ 56 ⋅ 6 mod 211
≡ 1872 ⋅ 182 ⋅ 56 ⋅ 6 mod 211 ≡ 184 ⋅ 182 ⋅ 56 ⋅ 6 mod 211
≡ 33488 ⋅ 56 ⋅ 6 mod 211 ≡ 150 ⋅ 56 ⋅ 6 mod 211
≡ 8400 ⋅ 6 mod 211 ≡ 171 ⋅ 6 mod 211
≡ 1026 mod 211 ≡ 182 mod 211

Es gilt also: 165²⁴² ≡ 182 mod 211

Berechnung des größten gemeinsamen Teilers von 97 und 92

=>97	= 1⋅92 + 5
=>92	= 18⋅5 + 2
=>5	= 2⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(97,92)=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= 5-2⋅2
2= 92-18⋅5	eingesetzt in die Zeile drüber:	1	= 1⋅5 -2⋅(92 -18⋅ 5) = 1⋅5 -2⋅92 +36⋅ 5) = -2⋅92 +37⋅ 5 (=1)
5= 97-1⋅92	eingesetzt in die Zeile drüber:	1	= -2⋅92 +37⋅(97 -1⋅ 92) = -2⋅92 +37⋅97 -37⋅ 92) = 37⋅97 -39⋅ 92 (=1)

Es gilt also: ggt(97,92)=1 = 37⋅97 -39⋅92

oder wenn man 37⋅97 auf die linke Seite bringt:

1 -37⋅97 = -39⋅92

-39⋅92 = -37⋅97 + 1 |+97⋅92

-39⋅92 + 97⋅92 = -37⋅97 + 97⋅92 + 1

(-39 + 97) ⋅ 92 = (-37 + 92) ⋅ 97 + 1

58⋅92 = 55⋅97 + 1

Es gilt also: 58⋅92 = 55⋅97 +1

Somit 58⋅92 = 1 mod 97

58 ist also das Inverse von 92 mod 97