Um längere Rechnungen zu vermeiden, rechnen wir:

(20993 + 21003) mod 7 ≡ (20993 mod 7 + 21003 mod 7) mod 7.

20993 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 20993 = 21000-7 = 7 ⋅ 3000 -7 = 7 ⋅ 3000 - 7 + 0.

21003 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 21003 = 21000+3 = 7 ⋅ 3000 +3.

Somit gilt:

(20993 + 21003) mod 7 ≡ (0 + 3) mod 7 ≡ 3 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(56 ⋅ 28) mod 6 ≡ (56 mod 6 ⋅ 28 mod 6) mod 6.

56 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 56 = 54 + 2 = 9 ⋅ 6 + 2 ist.

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

Somit gilt:

(56 ⋅ 28) mod 6 ≡ (2 ⋅ 4) mod 6 ≡ 8 mod 6 ≡ 2 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: 490¹=490

2: 490²=490¹⁺¹=490¹⋅490¹ ≡ 490⋅490=240100 ≡ 263 mod 971

4: 490⁴=490²⁺²=490²⋅490² ≡ 263⋅263=69169 ≡ 228 mod 971

8: 490⁸=490⁴⁺⁴=490⁴⋅490⁴ ≡ 228⋅228=51984 ≡ 521 mod 971

16: 490¹⁶=490⁸⁺⁸=490⁸⋅490⁸ ≡ 521⋅521=271441 ≡ 532 mod 971

32: 490³²=490¹⁶⁺¹⁶=490¹⁶⋅490¹⁶ ≡ 532⋅532=283024 ≡ 463 mod 971

64: 490⁶⁴=490³²⁺³²=490³²⋅490³² ≡ 463⋅463=214369 ≡ 749 mod 971

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

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

211 = 128+64+16+2+1

251²¹¹

= 251^{128+64+16+2+1}

= 251¹²⁸⋅251⁶⁴⋅251¹⁶⋅251²⋅251¹

≡ 412 ⋅ 288 ⋅ 112 ⋅ 224 ⋅ 251 mod 439
≡ 118656 ⋅ 112 ⋅ 224 ⋅ 251 mod 439 ≡ 126 ⋅ 112 ⋅ 224 ⋅ 251 mod 439
≡ 14112 ⋅ 224 ⋅ 251 mod 439 ≡ 64 ⋅ 224 ⋅ 251 mod 439
≡ 14336 ⋅ 251 mod 439 ≡ 288 ⋅ 251 mod 439
≡ 72288 mod 439 ≡ 292 mod 439

Es gilt also: 251²¹¹ ≡ 292 mod 439

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

=>97	= 1⋅58 + 39
=>58	= 1⋅39 + 19
=>39	= 2⋅19 + 1
=>19	= 19⋅1 + 0

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

Es gilt also: ggt(97,58)=1 = 3⋅97 -5⋅58

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

1 -3⋅97 = -5⋅58

-5⋅58 = -3⋅97 + 1 |+97⋅58

-5⋅58 + 97⋅58 = -3⋅97 + 97⋅58 + 1

(-5 + 97) ⋅ 58 = (-3 + 58) ⋅ 97 + 1

92⋅58 = 55⋅97 + 1

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

Somit 92⋅58 = 1 mod 97

92 ist also das Inverse von 58 mod 97