Um längere Rechnungen zu vermeiden, rechnen wir:

(3494 + 34993) mod 7 ≡ (3494 mod 7 + 34993 mod 7) mod 7.

3494 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 3494 = 3500-6 = 7 ⋅ 500 -6 = 7 ⋅ 500 - 7 + 1.

34993 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 34993 = 35000-7 = 7 ⋅ 5000 -7 = 7 ⋅ 5000 - 7 + 0.

Somit gilt:

(3494 + 34993) mod 7 ≡ (1 + 0) mod 7 ≡ 1 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(40 ⋅ 77) mod 4 ≡ (40 mod 4 ⋅ 77 mod 4) mod 4.

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

77 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 77 = 76 + 1 = 19 ⋅ 4 + 1 ist.

Somit gilt:

(40 ⋅ 77) mod 4 ≡ (0 ⋅ 1) mod 4 ≡ 0 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: 579¹=579

2: 579²=579¹⁺¹=579¹⋅579¹ ≡ 579⋅579=335241 ≡ 766 mod 787

4: 579⁴=579²⁺²=579²⋅579² ≡ 766⋅766=586756 ≡ 441 mod 787

8: 579⁸=579⁴⁺⁴=579⁴⋅579⁴ ≡ 441⋅441=194481 ≡ 92 mod 787

16: 579¹⁶=579⁸⁺⁸=579⁸⋅579⁸ ≡ 92⋅92=8464 ≡ 594 mod 787

32: 579³²=579¹⁶⁺¹⁶=579¹⁶⋅579¹⁶ ≡ 594⋅594=352836 ≡ 260 mod 787

64: 579⁶⁴=579³²⁺³²=579³²⋅579³² ≡ 260⋅260=67600 ≡ 705 mod 787

128: 579¹²⁸=579⁶⁴⁺⁶⁴=579⁶⁴⋅579⁶⁴ ≡ 705⋅705=497025 ≡ 428 mod 787

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

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

249 = 128+64+32+16+8+1

506²⁴⁹

= 506^{128+64+32+16+8+1}

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

≡ 49 ⋅ 564 ⋅ 317 ⋅ 51 ⋅ 529 ⋅ 506 mod 571
≡ 27636 ⋅ 317 ⋅ 51 ⋅ 529 ⋅ 506 mod 571 ≡ 228 ⋅ 317 ⋅ 51 ⋅ 529 ⋅ 506 mod 571
≡ 72276 ⋅ 51 ⋅ 529 ⋅ 506 mod 571 ≡ 330 ⋅ 51 ⋅ 529 ⋅ 506 mod 571
≡ 16830 ⋅ 529 ⋅ 506 mod 571 ≡ 271 ⋅ 529 ⋅ 506 mod 571
≡ 143359 ⋅ 506 mod 571 ≡ 38 ⋅ 506 mod 571
≡ 19228 mod 571 ≡ 385 mod 571

Es gilt also: 506²⁴⁹ ≡ 385 mod 571

Berechnung des größten gemeinsamen Teilers von 89 und 48

=>89	= 1⋅48 + 41
=>48	= 1⋅41 + 7
=>41	= 5⋅7 + 6
=>7	= 1⋅6 + 1
=>6	= 6⋅1 + 0

also gilt: ggt(89,48)=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-1⋅6
6= 41-5⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -1⋅(41 -5⋅ 7) = 1⋅7 -1⋅41 +5⋅ 7) = -1⋅41 +6⋅ 7 (=1)
7= 48-1⋅41	eingesetzt in die Zeile drüber:	1	= -1⋅41 +6⋅(48 -1⋅ 41) = -1⋅41 +6⋅48 -6⋅ 41) = 6⋅48 -7⋅ 41 (=1)
41= 89-1⋅48	eingesetzt in die Zeile drüber:	1	= 6⋅48 -7⋅(89 -1⋅ 48) = 6⋅48 -7⋅89 +7⋅ 48) = -7⋅89 +13⋅ 48 (=1)

Es gilt also: ggt(89,48)=1 = -7⋅89 +13⋅48

oder wenn man -7⋅89 auf die linke Seite bringt:

1 +7⋅89 = +13⋅48

Es gilt also: 13⋅48 = 7⋅89 +1

Somit 13⋅48 = 1 mod 89

13 ist also das Inverse von 48 mod 89