Um längere Rechnungen zu vermeiden, rechnen wir:

(28003 + 210) mod 7 ≡ (28003 mod 7 + 210 mod 7) mod 7.

28003 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 28003 = 28000+3 = 7 ⋅ 4000 +3.

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

Somit gilt:

(28003 + 210) mod 7 ≡ (3 + 0) mod 7 ≡ 3 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

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

79 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 79 = 77 + 2 = 11 ⋅ 7 + 2 ist.

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

Somit gilt:

(79 ⋅ 47) mod 7 ≡ (2 ⋅ 5) mod 7 ≡ 10 mod 7 ≡ 3 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: 270¹=270

2: 270²=270¹⁺¹=270¹⋅270¹ ≡ 270⋅270=72900 ≡ 113 mod 509

4: 270⁴=270²⁺²=270²⋅270² ≡ 113⋅113=12769 ≡ 44 mod 509

8: 270⁸=270⁴⁺⁴=270⁴⋅270⁴ ≡ 44⋅44=1936 ≡ 409 mod 509

16: 270¹⁶=270⁸⁺⁸=270⁸⋅270⁸ ≡ 409⋅409=167281 ≡ 329 mod 509

32: 270³²=270¹⁶⁺¹⁶=270¹⁶⋅270¹⁶ ≡ 329⋅329=108241 ≡ 333 mod 509

64: 270⁶⁴=270³²⁺³²=270³²⋅270³² ≡ 333⋅333=110889 ≡ 436 mod 509

128: 270¹²⁸=270⁶⁴⁺⁶⁴=270⁶⁴⋅270⁶⁴ ≡ 436⋅436=190096 ≡ 239 mod 509

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

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

225 = 128+64+32+1

568²²⁵

= 568^128+64+32+1

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

≡ 472 ⋅ 562 ⋅ 110 ⋅ 568 mod 641
≡ 265264 ⋅ 110 ⋅ 568 mod 641 ≡ 531 ⋅ 110 ⋅ 568 mod 641
≡ 58410 ⋅ 568 mod 641 ≡ 79 ⋅ 568 mod 641
≡ 44872 mod 641 ≡ 2 mod 641

Es gilt also: 568²²⁵ ≡ 2 mod 641

Berechnung des größten gemeinsamen Teilers von 101 und 85

=>101	= 1⋅85 + 16
=>85	= 5⋅16 + 5
=>16	= 3⋅5 + 1
=>5	= 5⋅1 + 0

also gilt: ggt(101,85)=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= 16-3⋅5
5= 85-5⋅16	eingesetzt in die Zeile drüber:	1	= 1⋅16 -3⋅(85 -5⋅ 16) = 1⋅16 -3⋅85 +15⋅ 16) = -3⋅85 +16⋅ 16 (=1)
16= 101-1⋅85	eingesetzt in die Zeile drüber:	1	= -3⋅85 +16⋅(101 -1⋅ 85) = -3⋅85 +16⋅101 -16⋅ 85) = 16⋅101 -19⋅ 85 (=1)

Es gilt also: ggt(101,85)=1 = 16⋅101 -19⋅85

oder wenn man 16⋅101 auf die linke Seite bringt:

1 -16⋅101 = -19⋅85

-19⋅85 = -16⋅101 + 1 |+101⋅85

-19⋅85 + 101⋅85 = -16⋅101 + 101⋅85 + 1

(-19 + 101) ⋅ 85 = (-16 + 85) ⋅ 101 + 1

82⋅85 = 69⋅101 + 1

Es gilt also: 82⋅85 = 69⋅101 +1

Somit 82⋅85 = 1 mod 101

82 ist also das Inverse von 85 mod 101