Um längere Rechnungen zu vermeiden, rechnen wir:

(353 - 7001) mod 7 ≡ (353 mod 7 - 7001 mod 7) mod 7.

353 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 353 = 350+3 = 7 ⋅ 50 +3.

7001 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 7001 = 7000+1 = 7 ⋅ 1000 +1.

Somit gilt:

(353 - 7001) mod 7 ≡ (3 - 1) mod 7 ≡ 2 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(52 ⋅ 82) mod 4 ≡ (52 mod 4 ⋅ 82 mod 4) mod 4.

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

82 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 82 = 80 + 2 = 20 ⋅ 4 + 2 ist.

Somit gilt:

(52 ⋅ 82) mod 4 ≡ (0 ⋅ 2) mod 4 ≡ 0 mod 4.

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

2: 470²=470¹⁺¹=470¹⋅470¹ ≡ 470⋅470=220900 ≡ 273 mod 647

4: 470⁴=470²⁺²=470²⋅470² ≡ 273⋅273=74529 ≡ 124 mod 647

8: 470⁸=470⁴⁺⁴=470⁴⋅470⁴ ≡ 124⋅124=15376 ≡ 495 mod 647

16: 470¹⁶=470⁸⁺⁸=470⁸⋅470⁸ ≡ 495⋅495=245025 ≡ 459 mod 647

32: 470³²=470¹⁶⁺¹⁶=470¹⁶⋅470¹⁶ ≡ 459⋅459=210681 ≡ 406 mod 647

64: 470⁶⁴=470³²⁺³²=470³²⋅470³² ≡ 406⋅406=164836 ≡ 498 mod 647

128: 470¹²⁸=470⁶⁴⁺⁶⁴=470⁶⁴⋅470⁶⁴ ≡ 498⋅498=248004 ≡ 203 mod 647

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

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

231 = 128+64+32+4+2+1

407²³¹

= 407^{128+64+32+4+2+1}

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

≡ 18 ⋅ 226 ⋅ 423 ⋅ 320 ⋅ 492 ⋅ 407 mod 521
≡ 4068 ⋅ 423 ⋅ 320 ⋅ 492 ⋅ 407 mod 521 ≡ 421 ⋅ 423 ⋅ 320 ⋅ 492 ⋅ 407 mod 521
≡ 178083 ⋅ 320 ⋅ 492 ⋅ 407 mod 521 ≡ 422 ⋅ 320 ⋅ 492 ⋅ 407 mod 521
≡ 135040 ⋅ 492 ⋅ 407 mod 521 ≡ 101 ⋅ 492 ⋅ 407 mod 521
≡ 49692 ⋅ 407 mod 521 ≡ 197 ⋅ 407 mod 521
≡ 80179 mod 521 ≡ 466 mod 521

Es gilt also: 407²³¹ ≡ 466 mod 521

Berechnung des größten gemeinsamen Teilers von 61 und 52

=>61	= 1⋅52 + 9
=>52	= 5⋅9 + 7
=>9	= 1⋅7 + 2
=>7	= 3⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(61,52)=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= 7-3⋅2
2= 9-1⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -3⋅(9 -1⋅ 7) = 1⋅7 -3⋅9 +3⋅ 7) = -3⋅9 +4⋅ 7 (=1)
7= 52-5⋅9	eingesetzt in die Zeile drüber:	1	= -3⋅9 +4⋅(52 -5⋅ 9) = -3⋅9 +4⋅52 -20⋅ 9) = 4⋅52 -23⋅ 9 (=1)
9= 61-1⋅52	eingesetzt in die Zeile drüber:	1	= 4⋅52 -23⋅(61 -1⋅ 52) = 4⋅52 -23⋅61 +23⋅ 52) = -23⋅61 +27⋅ 52 (=1)

Es gilt also: ggt(61,52)=1 = -23⋅61 +27⋅52

oder wenn man -23⋅61 auf die linke Seite bringt:

1 +23⋅61 = +27⋅52

Es gilt also: 27⋅52 = 23⋅61 +1

Somit 27⋅52 = 1 mod 61

27 ist also das Inverse von 52 mod 61