Um längere Rechnungen zu vermeiden, rechnen wir:

(20994 - 13993) mod 7 ≡ (20994 mod 7 - 13993 mod 7) mod 7.

20994 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 20994 = 21000-6 = 7 ⋅ 3000 -6 = 7 ⋅ 3000 - 7 + 1.

13993 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 13993 = 14000-7 = 7 ⋅ 2000 -7 = 7 ⋅ 2000 - 7 + 0.

Somit gilt:

(20994 - 13993) mod 7 ≡ (1 - 0) mod 7 ≡ 1 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(53 ⋅ 98) mod 4 ≡ (53 mod 4 ⋅ 98 mod 4) mod 4.

53 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 53 = 52 + 1 = 13 ⋅ 4 + 1 ist.

98 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 98 = 96 + 2 = 24 ⋅ 4 + 2 ist.

Somit gilt:

(53 ⋅ 98) mod 4 ≡ (1 ⋅ 2) mod 4 ≡ 2 mod 4.

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

2: 214²=214¹⁺¹=214¹⋅214¹ ≡ 214⋅214=45796 ≡ 18 mod 487

4: 214⁴=214²⁺²=214²⋅214² ≡ 18⋅18=324 ≡ 324 mod 487

8: 214⁸=214⁴⁺⁴=214⁴⋅214⁴ ≡ 324⋅324=104976 ≡ 271 mod 487

16: 214¹⁶=214⁸⁺⁸=214⁸⋅214⁸ ≡ 271⋅271=73441 ≡ 391 mod 487

32: 214³²=214¹⁶⁺¹⁶=214¹⁶⋅214¹⁶ ≡ 391⋅391=152881 ≡ 450 mod 487

64: 214⁶⁴=214³²⁺³²=214³²⋅214³² ≡ 450⋅450=202500 ≡ 395 mod 487

128: 214¹²⁸=214⁶⁴⁺⁶⁴=214⁶⁴⋅214⁶⁴ ≡ 395⋅395=156025 ≡ 185 mod 487

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

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

121 = 64+32+16+8+1

239¹²¹

= 239^64+32+16+8+1

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

≡ 421 ⋅ 68 ⋅ 423 ⋅ 251 ⋅ 239 mod 467
≡ 28628 ⋅ 423 ⋅ 251 ⋅ 239 mod 467 ≡ 141 ⋅ 423 ⋅ 251 ⋅ 239 mod 467
≡ 59643 ⋅ 251 ⋅ 239 mod 467 ≡ 334 ⋅ 251 ⋅ 239 mod 467
≡ 83834 ⋅ 239 mod 467 ≡ 241 ⋅ 239 mod 467
≡ 57599 mod 467 ≡ 158 mod 467

Es gilt also: 239¹²¹ ≡ 158 mod 467

Berechnung des größten gemeinsamen Teilers von 59 und 51

=>59	= 1⋅51 + 8
=>51	= 6⋅8 + 3
=>8	= 2⋅3 + 2
=>3	= 1⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(59,51)=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= 8-2⋅3	eingesetzt in die Zeile drüber:	1	= 1⋅3 -1⋅(8 -2⋅ 3) = 1⋅3 -1⋅8 +2⋅ 3) = -1⋅8 +3⋅ 3 (=1)
3= 51-6⋅8	eingesetzt in die Zeile drüber:	1	= -1⋅8 +3⋅(51 -6⋅ 8) = -1⋅8 +3⋅51 -18⋅ 8) = 3⋅51 -19⋅ 8 (=1)
8= 59-1⋅51	eingesetzt in die Zeile drüber:	1	= 3⋅51 -19⋅(59 -1⋅ 51) = 3⋅51 -19⋅59 +19⋅ 51) = -19⋅59 +22⋅ 51 (=1)

Es gilt also: ggt(59,51)=1 = -19⋅59 +22⋅51

oder wenn man -19⋅59 auf die linke Seite bringt:

1 +19⋅59 = +22⋅51

Es gilt also: 22⋅51 = 19⋅59 +1

Somit 22⋅51 = 1 mod 59

22 ist also das Inverse von 51 mod 59