Um längere Rechnungen zu vermeiden, rechnen wir:

(1201 - 1501) mod 3 ≡ (1201 mod 3 - 1501 mod 3) mod 3.

1201 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 1201 = 1200+1 = 3 ⋅ 400 +1.

1501 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 1501 = 1500+1 = 3 ⋅ 500 +1.

Somit gilt:

(1201 - 1501) mod 3 ≡ (1 - 1) mod 3 ≡ 0 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(29 ⋅ 84) mod 10 ≡ (29 mod 10 ⋅ 84 mod 10) mod 10.

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

84 mod 10 ≡ 4 mod 10 kann man relativ leicht bestimmen, weil ja 84 = 80 + 4 = 8 ⋅ 10 + 4 ist.

Somit gilt:

(29 ⋅ 84) mod 10 ≡ (9 ⋅ 4) mod 10 ≡ 36 mod 10 ≡ 6 mod 10.

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

2: 305²=305¹⁺¹=305¹⋅305¹ ≡ 305⋅305=93025 ≡ 175 mod 619

4: 305⁴=305²⁺²=305²⋅305² ≡ 175⋅175=30625 ≡ 294 mod 619

8: 305⁸=305⁴⁺⁴=305⁴⋅305⁴ ≡ 294⋅294=86436 ≡ 395 mod 619

16: 305¹⁶=305⁸⁺⁸=305⁸⋅305⁸ ≡ 395⋅395=156025 ≡ 37 mod 619

32: 305³²=305¹⁶⁺¹⁶=305¹⁶⋅305¹⁶ ≡ 37⋅37=1369 ≡ 131 mod 619

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

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

158 = 128+16+8+4+2

497¹⁵⁸

= 497^128+16+8+4+2

= 497¹²⁸⋅497¹⁶⋅497⁸⋅497⁴⋅497²

≡ 121 ⋅ 13 ⋅ 174 ⋅ 511 ⋅ 337 mod 571
≡ 1573 ⋅ 174 ⋅ 511 ⋅ 337 mod 571 ≡ 431 ⋅ 174 ⋅ 511 ⋅ 337 mod 571
≡ 74994 ⋅ 511 ⋅ 337 mod 571 ≡ 193 ⋅ 511 ⋅ 337 mod 571
≡ 98623 ⋅ 337 mod 571 ≡ 411 ⋅ 337 mod 571
≡ 138507 mod 571 ≡ 325 mod 571

Es gilt also: 497¹⁵⁸ ≡ 325 mod 571

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

=>101	= 1⋅88 + 13
=>88	= 6⋅13 + 10
=>13	= 1⋅10 + 3
=>10	= 3⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(101,88)=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= 10-3⋅3
3= 13-1⋅10	eingesetzt in die Zeile drüber:	1	= 1⋅10 -3⋅(13 -1⋅ 10) = 1⋅10 -3⋅13 +3⋅ 10) = -3⋅13 +4⋅ 10 (=1)
10= 88-6⋅13	eingesetzt in die Zeile drüber:	1	= -3⋅13 +4⋅(88 -6⋅ 13) = -3⋅13 +4⋅88 -24⋅ 13) = 4⋅88 -27⋅ 13 (=1)
13= 101-1⋅88	eingesetzt in die Zeile drüber:	1	= 4⋅88 -27⋅(101 -1⋅ 88) = 4⋅88 -27⋅101 +27⋅ 88) = -27⋅101 +31⋅ 88 (=1)

Es gilt also: ggt(101,88)=1 = -27⋅101 +31⋅88

oder wenn man -27⋅101 auf die linke Seite bringt:

1 +27⋅101 = +31⋅88

Es gilt also: 31⋅88 = 27⋅101 +1

Somit 31⋅88 = 1 mod 101

31 ist also das Inverse von 88 mod 101