Um längere Rechnungen zu vermeiden, rechnen wir:

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

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

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:

(35007 + 34993) mod 7 ≡ (0 + 0) mod 7 ≡ 0 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(61 ⋅ 81) mod 7 ≡ (61 mod 7 ⋅ 81 mod 7) mod 7.

61 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 61 = 56 + 5 = 8 ⋅ 7 + 5 ist.

81 mod 7 ≡ 4 mod 7 kann man relativ leicht bestimmen, weil ja 81 = 77 + 4 = 11 ⋅ 7 + 4 ist.

Somit gilt:

(61 ⋅ 81) mod 7 ≡ (5 ⋅ 4) mod 7 ≡ 20 mod 7 ≡ 6 mod 7.

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

2: 205²=205¹⁺¹=205¹⋅205¹ ≡ 205⋅205=42025 ≡ 18 mod 353

4: 205⁴=205²⁺²=205²⋅205² ≡ 18⋅18=324 ≡ 324 mod 353

8: 205⁸=205⁴⁺⁴=205⁴⋅205⁴ ≡ 324⋅324=104976 ≡ 135 mod 353

16: 205¹⁶=205⁸⁺⁸=205⁸⋅205⁸ ≡ 135⋅135=18225 ≡ 222 mod 353

32: 205³²=205¹⁶⁺¹⁶=205¹⁶⋅205¹⁶ ≡ 222⋅222=49284 ≡ 217 mod 353

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

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

213 = 128+64+16+4+1

413²¹³

= 413^{128+64+16+4+1}

= 413¹²⁸⋅413⁶⁴⋅413¹⁶⋅413⁴⋅413¹

≡ 413 ⋅ 156 ⋅ 238 ⋅ 371 ⋅ 413 mod 509
≡ 64428 ⋅ 238 ⋅ 371 ⋅ 413 mod 509 ≡ 294 ⋅ 238 ⋅ 371 ⋅ 413 mod 509
≡ 69972 ⋅ 371 ⋅ 413 mod 509 ≡ 239 ⋅ 371 ⋅ 413 mod 509
≡ 88669 ⋅ 413 mod 509 ≡ 103 ⋅ 413 mod 509
≡ 42539 mod 509 ≡ 292 mod 509

Es gilt also: 413²¹³ ≡ 292 mod 509

Berechnung des größten gemeinsamen Teilers von 101 und 55

=>101	= 1⋅55 + 46
=>55	= 1⋅46 + 9
=>46	= 5⋅9 + 1
=>9	= 9⋅1 + 0

also gilt: ggt(101,55)=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= 46-5⋅9
9= 55-1⋅46	eingesetzt in die Zeile drüber:	1	= 1⋅46 -5⋅(55 -1⋅ 46) = 1⋅46 -5⋅55 +5⋅ 46) = -5⋅55 +6⋅ 46 (=1)
46= 101-1⋅55	eingesetzt in die Zeile drüber:	1	= -5⋅55 +6⋅(101 -1⋅ 55) = -5⋅55 +6⋅101 -6⋅ 55) = 6⋅101 -11⋅ 55 (=1)

Es gilt also: ggt(101,55)=1 = 6⋅101 -11⋅55

oder wenn man 6⋅101 auf die linke Seite bringt:

1 -6⋅101 = -11⋅55

-11⋅55 = -6⋅101 + 1 |+101⋅55

-11⋅55 + 101⋅55 = -6⋅101 + 101⋅55 + 1

(-11 + 101) ⋅ 55 = (-6 + 55) ⋅ 101 + 1

90⋅55 = 49⋅101 + 1

Es gilt also: 90⋅55 = 49⋅101 +1

Somit 90⋅55 = 1 mod 101

90 ist also das Inverse von 55 mod 101