Um längere Rechnungen zu vermeiden, rechnen wir:

(34996 + 14005) mod 7 ≡ (34996 mod 7 + 14005 mod 7) mod 7.

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

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

Somit gilt:

(34996 + 14005) mod 7 ≡ (3 + 5) mod 7 ≡ 8 mod 7 ≡ 1 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(43 ⋅ 60) mod 4 ≡ (43 mod 4 ⋅ 60 mod 4) mod 4.

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

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

Somit gilt:

(43 ⋅ 60) mod 4 ≡ (3 ⋅ 0) mod 4 ≡ 0 mod 4.

Die 32 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: 427¹=427

2: 427²=427¹⁺¹=427¹⋅427¹ ≡ 427⋅427=182329 ≡ 256 mod 443

4: 427⁴=427²⁺²=427²⋅427² ≡ 256⋅256=65536 ≡ 415 mod 443

8: 427⁸=427⁴⁺⁴=427⁴⋅427⁴ ≡ 415⋅415=172225 ≡ 341 mod 443

16: 427¹⁶=427⁸⁺⁸=427⁸⋅427⁸ ≡ 341⋅341=116281 ≡ 215 mod 443

32: 427³²=427¹⁶⁺¹⁶=427¹⁶⋅427¹⁶ ≡ 215⋅215=46225 ≡ 153 mod 443

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

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

103 = 64+32+4+2+1

454¹⁰³

= 454^64+32+4+2+1

= 454⁶⁴⋅454³²⋅454⁴⋅454²⋅454¹

≡ 720 ⋅ 647 ⋅ 383 ⋅ 45 ⋅ 454 mod 821
≡ 465840 ⋅ 383 ⋅ 45 ⋅ 454 mod 821 ≡ 333 ⋅ 383 ⋅ 45 ⋅ 454 mod 821
≡ 127539 ⋅ 45 ⋅ 454 mod 821 ≡ 284 ⋅ 45 ⋅ 454 mod 821
≡ 12780 ⋅ 454 mod 821 ≡ 465 ⋅ 454 mod 821
≡ 211110 mod 821 ≡ 113 mod 821

Es gilt also: 454¹⁰³ ≡ 113 mod 821

Berechnung des größten gemeinsamen Teilers von 83 und 33

=>83	= 2⋅33 + 17
=>33	= 1⋅17 + 16
=>17	= 1⋅16 + 1
=>16	= 16⋅1 + 0

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

Es gilt also: ggt(83,33)=1 = 2⋅83 -5⋅33

oder wenn man 2⋅83 auf die linke Seite bringt:

1 -2⋅83 = -5⋅33

-5⋅33 = -2⋅83 + 1 |+83⋅33

-5⋅33 + 83⋅33 = -2⋅83 + 83⋅33 + 1

(-5 + 83) ⋅ 33 = (-2 + 33) ⋅ 83 + 1

78⋅33 = 31⋅83 + 1

Es gilt also: 78⋅33 = 31⋅83 +1

Somit 78⋅33 = 1 mod 83

78 ist also das Inverse von 33 mod 83