Um längere Rechnungen zu vermeiden, rechnen wir:

(343 + 35000) mod 7 ≡ (343 mod 7 + 35000 mod 7) mod 7.

343 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 343 = 350-7 = 7 ⋅ 50 -7 = 7 ⋅ 50 - 7 + 0.

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

Somit gilt:

(343 + 35000) mod 7 ≡ (0 + 0) mod 7 ≡ 0 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(92 ⋅ 73) mod 3 ≡ (92 mod 3 ⋅ 73 mod 3) mod 3.

92 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 92 = 90 + 2 = 30 ⋅ 3 + 2 ist.

73 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 73 = 72 + 1 = 24 ⋅ 3 + 1 ist.

Somit gilt:

(92 ⋅ 73) mod 3 ≡ (2 ⋅ 1) mod 3 ≡ 2 mod 3.

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

2: 436²=436¹⁺¹=436¹⋅436¹ ≡ 436⋅436=190096 ≡ 222 mod 683

4: 436⁴=436²⁺²=436²⋅436² ≡ 222⋅222=49284 ≡ 108 mod 683

8: 436⁸=436⁴⁺⁴=436⁴⋅436⁴ ≡ 108⋅108=11664 ≡ 53 mod 683

16: 436¹⁶=436⁸⁺⁸=436⁸⋅436⁸ ≡ 53⋅53=2809 ≡ 77 mod 683

32: 436³²=436¹⁶⁺¹⁶=436¹⁶⋅436¹⁶ ≡ 77⋅77=5929 ≡ 465 mod 683

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

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

174 = 128+32+8+4+2

402¹⁷⁴

= 402^128+32+8+4+2

= 402¹²⁸⋅402³²⋅402⁸⋅402⁴⋅402²

≡ 381 ⋅ 320 ⋅ 381 ⋅ 606 ⋅ 320 mod 661
≡ 121920 ⋅ 381 ⋅ 606 ⋅ 320 mod 661 ≡ 296 ⋅ 381 ⋅ 606 ⋅ 320 mod 661
≡ 112776 ⋅ 606 ⋅ 320 mod 661 ≡ 406 ⋅ 606 ⋅ 320 mod 661
≡ 246036 ⋅ 320 mod 661 ≡ 144 ⋅ 320 mod 661
≡ 46080 mod 661 ≡ 471 mod 661

Es gilt also: 402¹⁷⁴ ≡ 471 mod 661

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

=>101	= 1⋅85 + 16
=>85	= 5⋅16 + 5
=>16	= 3⋅5 + 1
=>5	= 5⋅1 + 0

also gilt: ggt(101,85)=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= 16-3⋅5
5= 85-5⋅16	eingesetzt in die Zeile drüber:	1	= 1⋅16 -3⋅(85 -5⋅ 16) = 1⋅16 -3⋅85 +15⋅ 16) = -3⋅85 +16⋅ 16 (=1)
16= 101-1⋅85	eingesetzt in die Zeile drüber:	1	= -3⋅85 +16⋅(101 -1⋅ 85) = -3⋅85 +16⋅101 -16⋅ 85) = 16⋅101 -19⋅ 85 (=1)

Es gilt also: ggt(101,85)=1 = 16⋅101 -19⋅85

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

1 -16⋅101 = -19⋅85

-19⋅85 = -16⋅101 + 1 |+101⋅85

-19⋅85 + 101⋅85 = -16⋅101 + 101⋅85 + 1

(-19 + 101) ⋅ 85 = (-16 + 85) ⋅ 101 + 1

82⋅85 = 69⋅101 + 1

Es gilt also: 82⋅85 = 69⋅101 +1

Somit 82⋅85 = 1 mod 101

82 ist also das Inverse von 85 mod 101