Um längere Rechnungen zu vermeiden, rechnen wir:

(404 - 12004) mod 4 ≡ (404 mod 4 - 12004 mod 4) mod 4.

404 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 404 = 400+4 = 4 ⋅ 100 +4.

12004 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 12004 = 12000+4 = 4 ⋅ 3000 +4.

Somit gilt:

(404 - 12004) mod 4 ≡ (0 - 0) mod 4 ≡ 0 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(45 ⋅ 24) mod 6 ≡ (45 mod 6 ⋅ 24 mod 6) mod 6.

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

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

Somit gilt:

(45 ⋅ 24) mod 6 ≡ (3 ⋅ 0) mod 6 ≡ 0 mod 6.

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

2: 680²=680¹⁺¹=680¹⋅680¹ ≡ 680⋅680=462400 ≡ 273 mod 887

4: 680⁴=680²⁺²=680²⋅680² ≡ 273⋅273=74529 ≡ 21 mod 887

8: 680⁸=680⁴⁺⁴=680⁴⋅680⁴ ≡ 21⋅21=441 ≡ 441 mod 887

16: 680¹⁶=680⁸⁺⁸=680⁸⋅680⁸ ≡ 441⋅441=194481 ≡ 228 mod 887

32: 680³²=680¹⁶⁺¹⁶=680¹⁶⋅680¹⁶ ≡ 228⋅228=51984 ≡ 538 mod 887

64: 680⁶⁴=680³²⁺³²=680³²⋅680³² ≡ 538⋅538=289444 ≡ 282 mod 887

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

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

103 = 64+32+4+2+1

973¹⁰³

= 973^64+32+4+2+1

= 973⁶⁴⋅973³²⋅973⁴⋅973²⋅973¹

≡ 18 ⋅ 722 ⋅ 921 ⋅ 324 ⋅ 973 mod 991
≡ 12996 ⋅ 921 ⋅ 324 ⋅ 973 mod 991 ≡ 113 ⋅ 921 ⋅ 324 ⋅ 973 mod 991
≡ 104073 ⋅ 324 ⋅ 973 mod 991 ≡ 18 ⋅ 324 ⋅ 973 mod 991
≡ 5832 ⋅ 973 mod 991 ≡ 877 ⋅ 973 mod 991
≡ 853321 mod 991 ≡ 70 mod 991

Es gilt also: 973¹⁰³ ≡ 70 mod 991

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

=>53	= 2⋅22 + 9
=>22	= 2⋅9 + 4
=>9	= 2⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(53,22)=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= 9-2⋅4
4= 22-2⋅9	eingesetzt in die Zeile drüber:	1	= 1⋅9 -2⋅(22 -2⋅ 9) = 1⋅9 -2⋅22 +4⋅ 9) = -2⋅22 +5⋅ 9 (=1)
9= 53-2⋅22	eingesetzt in die Zeile drüber:	1	= -2⋅22 +5⋅(53 -2⋅ 22) = -2⋅22 +5⋅53 -10⋅ 22) = 5⋅53 -12⋅ 22 (=1)

Es gilt also: ggt(53,22)=1 = 5⋅53 -12⋅22

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

1 -5⋅53 = -12⋅22

-12⋅22 = -5⋅53 + 1 |+53⋅22

-12⋅22 + 53⋅22 = -5⋅53 + 53⋅22 + 1

(-12 + 53) ⋅ 22 = (-5 + 22) ⋅ 53 + 1

41⋅22 = 17⋅53 + 1

Es gilt also: 41⋅22 = 17⋅53 +1

Somit 41⋅22 = 1 mod 53

41 ist also das Inverse von 22 mod 53