Um längere Rechnungen zu vermeiden, rechnen wir:

(3505 - 64) mod 7 ≡ (3505 mod 7 - 64 mod 7) mod 7.

3505 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 3505 = 3500+5 = 7 ⋅ 500 +5.

64 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 64 = 70-6 = 7 ⋅ 10 -6 = 7 ⋅ 10 - 7 + 1.

Somit gilt:

(3505 - 64) mod 7 ≡ (5 - 1) mod 7 ≡ 4 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(15 ⋅ 52) mod 10 ≡ (15 mod 10 ⋅ 52 mod 10) mod 10.

15 mod 10 ≡ 5 mod 10 kann man relativ leicht bestimmen, weil ja 15 = 10 + 5 = 1 ⋅ 10 + 5 ist.

52 mod 10 ≡ 2 mod 10 kann man relativ leicht bestimmen, weil ja 52 = 50 + 2 = 5 ⋅ 10 + 2 ist.

Somit gilt:

(15 ⋅ 52) mod 10 ≡ (5 ⋅ 2) mod 10 ≡ 10 mod 10 ≡ 0 mod 10.

Die 16 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: 186¹=186

2: 186²=186¹⁺¹=186¹⋅186¹ ≡ 186⋅186=34596 ≡ 22 mod 293

4: 186⁴=186²⁺²=186²⋅186² ≡ 22⋅22=484 ≡ 191 mod 293

8: 186⁸=186⁴⁺⁴=186⁴⋅186⁴ ≡ 191⋅191=36481 ≡ 149 mod 293

16: 186¹⁶=186⁸⁺⁸=186⁸⋅186⁸ ≡ 149⋅149=22201 ≡ 226 mod 293

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

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

63 = 32+16+8+4+2+1

217⁶³

= 217^{32+16+8+4+2+1}

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

≡ 406 ⋅ 552 ⋅ 577 ⋅ 105 ⋅ 73 ⋅ 217 mod 653
≡ 224112 ⋅ 577 ⋅ 105 ⋅ 73 ⋅ 217 mod 653 ≡ 133 ⋅ 577 ⋅ 105 ⋅ 73 ⋅ 217 mod 653
≡ 76741 ⋅ 105 ⋅ 73 ⋅ 217 mod 653 ≡ 340 ⋅ 105 ⋅ 73 ⋅ 217 mod 653
≡ 35700 ⋅ 73 ⋅ 217 mod 653 ≡ 438 ⋅ 73 ⋅ 217 mod 653
≡ 31974 ⋅ 217 mod 653 ≡ 630 ⋅ 217 mod 653
≡ 136710 mod 653 ≡ 233 mod 653

Es gilt also: 217⁶³ ≡ 233 mod 653

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

=>61	= 2⋅22 + 17
=>22	= 1⋅17 + 5
=>17	= 3⋅5 + 2
=>5	= 2⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(61,22)=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-2⋅2
2= 17-3⋅5	eingesetzt in die Zeile drüber:	1	= 1⋅5 -2⋅(17 -3⋅ 5) = 1⋅5 -2⋅17 +6⋅ 5) = -2⋅17 +7⋅ 5 (=1)
5= 22-1⋅17	eingesetzt in die Zeile drüber:	1	= -2⋅17 +7⋅(22 -1⋅ 17) = -2⋅17 +7⋅22 -7⋅ 17) = 7⋅22 -9⋅ 17 (=1)
17= 61-2⋅22	eingesetzt in die Zeile drüber:	1	= 7⋅22 -9⋅(61 -2⋅ 22) = 7⋅22 -9⋅61 +18⋅ 22) = -9⋅61 +25⋅ 22 (=1)

Es gilt also: ggt(61,22)=1 = -9⋅61 +25⋅22

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

1 +9⋅61 = +25⋅22

Es gilt also: 25⋅22 = 9⋅61 +1

Somit 25⋅22 = 1 mod 61

25 ist also das Inverse von 22 mod 61