Um längere Rechnungen zu vermeiden, rechnen wir:

(35007 + 279) mod 7 ≡ (35007 mod 7 + 279 mod 7) mod 7.

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

279 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 279 = 280-1 = 7 ⋅ 40 -1 = 7 ⋅ 40 - 7 + 6.

Somit gilt:

(35007 + 279) mod 7 ≡ (0 + 6) mod 7 ≡ 6 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(83 ⋅ 28) mod 8 ≡ (83 mod 8 ⋅ 28 mod 8) mod 8.

83 mod 8 ≡ 3 mod 8 kann man relativ leicht bestimmen, weil ja 83 = 80 + 3 = 10 ⋅ 8 + 3 ist.

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

Somit gilt:

(83 ⋅ 28) mod 8 ≡ (3 ⋅ 4) mod 8 ≡ 12 mod 8 ≡ 4 mod 8.

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

2: 596²=596¹⁺¹=596¹⋅596¹ ≡ 596⋅596=355216 ≡ 30 mod 719

4: 596⁴=596²⁺²=596²⋅596² ≡ 30⋅30=900 ≡ 181 mod 719

8: 596⁸=596⁴⁺⁴=596⁴⋅596⁴ ≡ 181⋅181=32761 ≡ 406 mod 719

16: 596¹⁶=596⁸⁺⁸=596⁸⋅596⁸ ≡ 406⋅406=164836 ≡ 185 mod 719

32: 596³²=596¹⁶⁺¹⁶=596¹⁶⋅596¹⁶ ≡ 185⋅185=34225 ≡ 432 mod 719

64: 596⁶⁴=596³²⁺³²=596³²⋅596³² ≡ 432⋅432=186624 ≡ 403 mod 719

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

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

238 = 128+64+32+8+4+2

152²³⁸

= 152^{128+64+32+8+4+2}

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

≡ 270 ⋅ 318 ⋅ 230 ⋅ 98 ⋅ 23 ⋅ 261 mod 431
≡ 85860 ⋅ 230 ⋅ 98 ⋅ 23 ⋅ 261 mod 431 ≡ 91 ⋅ 230 ⋅ 98 ⋅ 23 ⋅ 261 mod 431
≡ 20930 ⋅ 98 ⋅ 23 ⋅ 261 mod 431 ≡ 242 ⋅ 98 ⋅ 23 ⋅ 261 mod 431
≡ 23716 ⋅ 23 ⋅ 261 mod 431 ≡ 11 ⋅ 23 ⋅ 261 mod 431
≡ 253 ⋅ 261 mod 431
≡ 66033 mod 431 ≡ 90 mod 431

Es gilt also: 152²³⁸ ≡ 90 mod 431

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

=>83	= 2⋅39 + 5
=>39	= 7⋅5 + 4
=>5	= 1⋅4 + 1
=>4	= 4⋅1 + 0

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

Es gilt also: ggt(83,39)=1 = 8⋅83 -17⋅39

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

1 -8⋅83 = -17⋅39

-17⋅39 = -8⋅83 + 1 |+83⋅39

-17⋅39 + 83⋅39 = -8⋅83 + 83⋅39 + 1

(-17 + 83) ⋅ 39 = (-8 + 39) ⋅ 83 + 1

66⋅39 = 31⋅83 + 1

Es gilt also: 66⋅39 = 31⋅83 +1

Somit 66⋅39 = 1 mod 83

66 ist also das Inverse von 39 mod 83