Um längere Rechnungen zu vermeiden, rechnen wir:

(999 + 4999) mod 5 ≡ (999 mod 5 + 4999 mod 5) mod 5.

999 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 999 = 900+99 = 5 ⋅ 180 +99.

4999 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 4999 = 4000+999 = 5 ⋅ 800 +999.

Somit gilt:

(999 + 4999) mod 5 ≡ (4 + 4) mod 5 ≡ 8 mod 5 ≡ 3 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(91 ⋅ 28) mod 10 ≡ (91 mod 10 ⋅ 28 mod 10) mod 10.

91 mod 10 ≡ 1 mod 10 kann man relativ leicht bestimmen, weil ja 91 = 90 + 1 = 9 ⋅ 10 + 1 ist.

28 mod 10 ≡ 8 mod 10 kann man relativ leicht bestimmen, weil ja 28 = 20 + 8 = 2 ⋅ 10 + 8 ist.

Somit gilt:

(91 ⋅ 28) mod 10 ≡ (1 ⋅ 8) mod 10 ≡ 8 mod 10.

Die 16 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: 433¹=433

2: 433²=433¹⁺¹=433¹⋅433¹ ≡ 433⋅433=187489 ≡ 858 mod 967

4: 433⁴=433²⁺²=433²⋅433² ≡ 858⋅858=736164 ≡ 277 mod 967

8: 433⁸=433⁴⁺⁴=433⁴⋅433⁴ ≡ 277⋅277=76729 ≡ 336 mod 967

16: 433¹⁶=433⁸⁺⁸=433⁸⋅433⁸ ≡ 336⋅336=112896 ≡ 724 mod 967

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

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

220 = 128+64+16+8+4

134²²⁰

= 134^{128+64+16+8+4}

= 134¹²⁸⋅134⁶⁴⋅134¹⁶⋅134⁸⋅134⁴

≡ 94 ⋅ 134 ⋅ 134 ⋅ 94 ⋅ 134 mod 229
≡ 12596 ⋅ 134 ⋅ 94 ⋅ 134 mod 229 ≡ 1 ⋅ 134 ⋅ 94 ⋅ 134 mod 229
≡ 134 ⋅ 94 ⋅ 134 mod 229
≡ 12596 ⋅ 134 mod 229 ≡ 1 ⋅ 134 mod 229
≡ 134 mod 229

Es gilt also: 134²²⁰ ≡ 134 mod 229

Berechnung des größten gemeinsamen Teilers von 53 und 28

=>53	= 1⋅28 + 25
=>28	= 1⋅25 + 3
=>25	= 8⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(53,28)=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= 25-8⋅3
3= 28-1⋅25	eingesetzt in die Zeile drüber:	1	= 1⋅25 -8⋅(28 -1⋅ 25) = 1⋅25 -8⋅28 +8⋅ 25) = -8⋅28 +9⋅ 25 (=1)
25= 53-1⋅28	eingesetzt in die Zeile drüber:	1	= -8⋅28 +9⋅(53 -1⋅ 28) = -8⋅28 +9⋅53 -9⋅ 28) = 9⋅53 -17⋅ 28 (=1)

Es gilt also: ggt(53,28)=1 = 9⋅53 -17⋅28

oder wenn man 9⋅53 auf die linke Seite bringt:

1 -9⋅53 = -17⋅28

-17⋅28 = -9⋅53 + 1 |+53⋅28

-17⋅28 + 53⋅28 = -9⋅53 + 53⋅28 + 1

(-17 + 53) ⋅ 28 = (-9 + 28) ⋅ 53 + 1

36⋅28 = 19⋅53 + 1

Es gilt also: 36⋅28 = 19⋅53 +1

Somit 36⋅28 = 1 mod 53

36 ist also das Inverse von 28 mod 53