Um längere Rechnungen zu vermeiden, rechnen wir:

(2005 - 155) mod 5 ≡ (2005 mod 5 - 155 mod 5) mod 5.

2005 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 2005 = 2000+5 = 5 ⋅ 400 +5.

155 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 155 = 150+5 = 5 ⋅ 30 +5.

Somit gilt:

(2005 - 155) mod 5 ≡ (0 - 0) mod 5 ≡ 0 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(23 ⋅ 18) mod 10 ≡ (23 mod 10 ⋅ 18 mod 10) mod 10.

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

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

Somit gilt:

(23 ⋅ 18) mod 10 ≡ (3 ⋅ 8) mod 10 ≡ 24 mod 10 ≡ 4 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: 264¹=264

2: 264²=264¹⁺¹=264¹⋅264¹ ≡ 264⋅264=69696 ≡ 113 mod 467

4: 264⁴=264²⁺²=264²⋅264² ≡ 113⋅113=12769 ≡ 160 mod 467

8: 264⁸=264⁴⁺⁴=264⁴⋅264⁴ ≡ 160⋅160=25600 ≡ 382 mod 467

16: 264¹⁶=264⁸⁺⁸=264⁸⋅264⁸ ≡ 382⋅382=145924 ≡ 220 mod 467

32: 264³²=264¹⁶⁺¹⁶=264¹⁶⋅264¹⁶ ≡ 220⋅220=48400 ≡ 299 mod 467

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

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

212 = 128+64+16+4

510²¹²

= 510^128+64+16+4

= 510¹²⁸⋅510⁶⁴⋅510¹⁶⋅510⁴

≡ 562 ⋅ 531 ⋅ 255 ⋅ 163 mod 641
≡ 298422 ⋅ 255 ⋅ 163 mod 641 ≡ 357 ⋅ 255 ⋅ 163 mod 641
≡ 91035 ⋅ 163 mod 641 ≡ 13 ⋅ 163 mod 641
≡ 2119 mod 641 ≡ 196 mod 641

Es gilt also: 510²¹² ≡ 196 mod 641

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