Um längere Rechnungen zu vermeiden, rechnen wir:

(13998 + 35006) mod 7 ≡ (13998 mod 7 + 35006 mod 7) mod 7.

13998 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 13998 = 14000-2 = 7 ⋅ 2000 -2 = 7 ⋅ 2000 - 7 + 5.

35006 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 35006 = 35000+6 = 7 ⋅ 5000 +6.

Somit gilt:

(13998 + 35006) mod 7 ≡ (5 + 6) mod 7 ≡ 11 mod 7 ≡ 4 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(18 ⋅ 41) mod 9 ≡ (18 mod 9 ⋅ 41 mod 9) mod 9.

18 mod 9 ≡ 0 mod 9 kann man relativ leicht bestimmen, weil ja 18 = 18 + 0 = 2 ⋅ 9 + 0 ist.

41 mod 9 ≡ 5 mod 9 kann man relativ leicht bestimmen, weil ja 41 = 36 + 5 = 4 ⋅ 9 + 5 ist.

Somit gilt:

(18 ⋅ 41) mod 9 ≡ (0 ⋅ 5) mod 9 ≡ 0 mod 9.

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

2: 592²=592¹⁺¹=592¹⋅592¹ ≡ 592⋅592=350464 ≡ 713 mod 953

4: 592⁴=592²⁺²=592²⋅592² ≡ 713⋅713=508369 ≡ 420 mod 953

8: 592⁸=592⁴⁺⁴=592⁴⋅592⁴ ≡ 420⋅420=176400 ≡ 95 mod 953

16: 592¹⁶=592⁸⁺⁸=592⁸⋅592⁸ ≡ 95⋅95=9025 ≡ 448 mod 953

32: 592³²=592¹⁶⁺¹⁶=592¹⁶⋅592¹⁶ ≡ 448⋅448=200704 ≡ 574 mod 953

64: 592⁶⁴=592³²⁺³²=592³²⋅592³² ≡ 574⋅574=329476 ≡ 691 mod 953

128: 592¹²⁸=592⁶⁴⁺⁶⁴=592⁶⁴⋅592⁶⁴ ≡ 691⋅691=477481 ≡ 28 mod 953

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

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

111 = 64+32+8+4+2+1

466¹¹¹

= 466^{64+32+8+4+2+1}

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

≡ 161 ⋅ 277 ⋅ 360 ⋅ 346 ⋅ 401 ⋅ 466 mod 563
≡ 44597 ⋅ 360 ⋅ 346 ⋅ 401 ⋅ 466 mod 563 ≡ 120 ⋅ 360 ⋅ 346 ⋅ 401 ⋅ 466 mod 563
≡ 43200 ⋅ 346 ⋅ 401 ⋅ 466 mod 563 ≡ 412 ⋅ 346 ⋅ 401 ⋅ 466 mod 563
≡ 142552 ⋅ 401 ⋅ 466 mod 563 ≡ 113 ⋅ 401 ⋅ 466 mod 563
≡ 45313 ⋅ 466 mod 563 ≡ 273 ⋅ 466 mod 563
≡ 127218 mod 563 ≡ 543 mod 563

Es gilt also: 466¹¹¹ ≡ 543 mod 563

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

=>59	= 1⋅42 + 17
=>42	= 2⋅17 + 8
=>17	= 2⋅8 + 1
=>8	= 8⋅1 + 0

also gilt: ggt(59,42)=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= 17-2⋅8
8= 42-2⋅17	eingesetzt in die Zeile drüber:	1	= 1⋅17 -2⋅(42 -2⋅ 17) = 1⋅17 -2⋅42 +4⋅ 17) = -2⋅42 +5⋅ 17 (=1)
17= 59-1⋅42	eingesetzt in die Zeile drüber:	1	= -2⋅42 +5⋅(59 -1⋅ 42) = -2⋅42 +5⋅59 -5⋅ 42) = 5⋅59 -7⋅ 42 (=1)

Es gilt also: ggt(59,42)=1 = 5⋅59 -7⋅42

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

1 -5⋅59 = -7⋅42

-7⋅42 = -5⋅59 + 1 |+59⋅42

-7⋅42 + 59⋅42 = -5⋅59 + 59⋅42 + 1

(-7 + 59) ⋅ 42 = (-5 + 42) ⋅ 59 + 1

52⋅42 = 37⋅59 + 1

Es gilt also: 52⋅42 = 37⋅59 +1

Somit 52⋅42 = 1 mod 59

52 ist also das Inverse von 42 mod 59