Um längere Rechnungen zu vermeiden, rechnen wir:

(20993 - 34996) mod 7 ≡ (20993 mod 7 - 34996 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.

34996 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 34996 = 35000-4 = 7 ⋅ 5000 -4 = 7 ⋅ 5000 - 7 + 3.

Somit gilt:

(20993 - 34996) mod 7 ≡ (0 - 3) mod 7 ≡ -3 mod 7 ≡ 4 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(68 ⋅ 66) mod 6 ≡ (68 mod 6 ⋅ 66 mod 6) mod 6.

68 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 68 = 66 + 2 = 11 ⋅ 6 + 2 ist.

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

Somit gilt:

(68 ⋅ 66) mod 6 ≡ (2 ⋅ 0) mod 6 ≡ 0 mod 6.

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

2: 657²=657¹⁺¹=657¹⋅657¹ ≡ 657⋅657=431649 ≡ 403 mod 839

4: 657⁴=657²⁺²=657²⋅657² ≡ 403⋅403=162409 ≡ 482 mod 839

8: 657⁸=657⁴⁺⁴=657⁴⋅657⁴ ≡ 482⋅482=232324 ≡ 760 mod 839

16: 657¹⁶=657⁸⁺⁸=657⁸⋅657⁸ ≡ 760⋅760=577600 ≡ 368 mod 839

32: 657³²=657¹⁶⁺¹⁶=657¹⁶⋅657¹⁶ ≡ 368⋅368=135424 ≡ 345 mod 839

64: 657⁶⁴=657³²⁺³²=657³²⋅657³² ≡ 345⋅345=119025 ≡ 726 mod 839

128: 657¹²⁸=657⁶⁴⁺⁶⁴=657⁶⁴⋅657⁶⁴ ≡ 726⋅726=527076 ≡ 184 mod 839

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

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

252 = 128+64+32+16+8+4

713²⁵²

= 713^{128+64+32+16+8+4}

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

≡ 808 ⋅ 295 ⋅ 79 ⋅ 775 ⋅ 758 ⋅ 196 mod 991
≡ 238360 ⋅ 79 ⋅ 775 ⋅ 758 ⋅ 196 mod 991 ≡ 520 ⋅ 79 ⋅ 775 ⋅ 758 ⋅ 196 mod 991
≡ 41080 ⋅ 775 ⋅ 758 ⋅ 196 mod 991 ≡ 449 ⋅ 775 ⋅ 758 ⋅ 196 mod 991
≡ 347975 ⋅ 758 ⋅ 196 mod 991 ≡ 134 ⋅ 758 ⋅ 196 mod 991
≡ 101572 ⋅ 196 mod 991 ≡ 490 ⋅ 196 mod 991
≡ 96040 mod 991 ≡ 904 mod 991

Es gilt also: 713²⁵² ≡ 904 mod 991

Berechnung des größten gemeinsamen Teilers von 67 und 57

=>67	= 1⋅57 + 10
=>57	= 5⋅10 + 7
=>10	= 1⋅7 + 3
=>7	= 2⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(67,57)=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= 7-2⋅3
3= 10-1⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -2⋅(10 -1⋅ 7) = 1⋅7 -2⋅10 +2⋅ 7) = -2⋅10 +3⋅ 7 (=1)
7= 57-5⋅10	eingesetzt in die Zeile drüber:	1	= -2⋅10 +3⋅(57 -5⋅ 10) = -2⋅10 +3⋅57 -15⋅ 10) = 3⋅57 -17⋅ 10 (=1)
10= 67-1⋅57	eingesetzt in die Zeile drüber:	1	= 3⋅57 -17⋅(67 -1⋅ 57) = 3⋅57 -17⋅67 +17⋅ 57) = -17⋅67 +20⋅ 57 (=1)

Es gilt also: ggt(67,57)=1 = -17⋅67 +20⋅57

oder wenn man -17⋅67 auf die linke Seite bringt:

1 +17⋅67 = +20⋅57

Es gilt also: 20⋅57 = 17⋅67 +1

Somit 20⋅57 = 1 mod 67

20 ist also das Inverse von 57 mod 67