Um längere Rechnungen zu vermeiden, rechnen wir:

(61 + 303) mod 3 ≡ (61 mod 3 + 303 mod 3) mod 3.

61 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 61 = 60+1 = 3 ⋅ 20 +1.

303 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 303 = 300+3 = 3 ⋅ 100 +3.

Somit gilt:

(61 + 303) mod 3 ≡ (1 + 0) mod 3 ≡ 1 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(45 ⋅ 22) mod 10 ≡ (45 mod 10 ⋅ 22 mod 10) mod 10.

45 mod 10 ≡ 5 mod 10 kann man relativ leicht bestimmen, weil ja 45 = 40 + 5 = 4 ⋅ 10 + 5 ist.

22 mod 10 ≡ 2 mod 10 kann man relativ leicht bestimmen, weil ja 22 = 20 + 2 = 2 ⋅ 10 + 2 ist.

Somit gilt:

(45 ⋅ 22) 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: 184¹=184

2: 184²=184¹⁺¹=184¹⋅184¹ ≡ 184⋅184=33856 ≡ 197 mod 347

4: 184⁴=184²⁺²=184²⋅184² ≡ 197⋅197=38809 ≡ 292 mod 347

8: 184⁸=184⁴⁺⁴=184⁴⋅184⁴ ≡ 292⋅292=85264 ≡ 249 mod 347

16: 184¹⁶=184⁸⁺⁸=184⁸⋅184⁸ ≡ 249⋅249=62001 ≡ 235 mod 347

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

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

181 = 128+32+16+4+1

537¹⁸¹

= 537^{128+32+16+4+1}

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

≡ 137 ⋅ 240 ⋅ 215 ⋅ 256 ⋅ 537 mod 541
≡ 32880 ⋅ 215 ⋅ 256 ⋅ 537 mod 541 ≡ 420 ⋅ 215 ⋅ 256 ⋅ 537 mod 541
≡ 90300 ⋅ 256 ⋅ 537 mod 541 ≡ 494 ⋅ 256 ⋅ 537 mod 541
≡ 126464 ⋅ 537 mod 541 ≡ 411 ⋅ 537 mod 541
≡ 220707 mod 541 ≡ 520 mod 541

Es gilt also: 537¹⁸¹ ≡ 520 mod 541

Berechnung des größten gemeinsamen Teilers von 89 und 70

=>89	= 1⋅70 + 19
=>70	= 3⋅19 + 13
=>19	= 1⋅13 + 6
=>13	= 2⋅6 + 1
=>6	= 6⋅1 + 0

also gilt: ggt(89,70)=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= 13-2⋅6
6= 19-1⋅13	eingesetzt in die Zeile drüber:	1	= 1⋅13 -2⋅(19 -1⋅ 13) = 1⋅13 -2⋅19 +2⋅ 13) = -2⋅19 +3⋅ 13 (=1)
13= 70-3⋅19	eingesetzt in die Zeile drüber:	1	= -2⋅19 +3⋅(70 -3⋅ 19) = -2⋅19 +3⋅70 -9⋅ 19) = 3⋅70 -11⋅ 19 (=1)
19= 89-1⋅70	eingesetzt in die Zeile drüber:	1	= 3⋅70 -11⋅(89 -1⋅ 70) = 3⋅70 -11⋅89 +11⋅ 70) = -11⋅89 +14⋅ 70 (=1)

Es gilt also: ggt(89,70)=1 = -11⋅89 +14⋅70

oder wenn man -11⋅89 auf die linke Seite bringt:

1 +11⋅89 = +14⋅70

Es gilt also: 14⋅70 = 11⋅89 +1

Somit 14⋅70 = 1 mod 89

14 ist also das Inverse von 70 mod 89