Um längere Rechnungen zu vermeiden, rechnen wir:

(1602 + 1604) mod 8 ≡ (1602 mod 8 + 1604 mod 8) mod 8.

1602 mod 8 ≡ 2 mod 8 kann man relativ leicht bestimmen, weil ja 1602 = 1600+2 = 8 ⋅ 200 +2.

1604 mod 8 ≡ 4 mod 8 kann man relativ leicht bestimmen, weil ja 1604 = 1600+4 = 8 ⋅ 200 +4.

Somit gilt:

(1602 + 1604) mod 8 ≡ (2 + 4) mod 8 ≡ 6 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(36 ⋅ 91) mod 5 ≡ (36 mod 5 ⋅ 91 mod 5) mod 5.

36 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 36 = 35 + 1 = 7 ⋅ 5 + 1 ist.

91 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 91 = 90 + 1 = 18 ⋅ 5 + 1 ist.

Somit gilt:

(36 ⋅ 91) mod 5 ≡ (1 ⋅ 1) mod 5 ≡ 1 mod 5.

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

2: 251²=251¹⁺¹=251¹⋅251¹ ≡ 251⋅251=63001 ≡ 75 mod 431

4: 251⁴=251²⁺²=251²⋅251² ≡ 75⋅75=5625 ≡ 22 mod 431

8: 251⁸=251⁴⁺⁴=251⁴⋅251⁴ ≡ 22⋅22=484 ≡ 53 mod 431

16: 251¹⁶=251⁸⁺⁸=251⁸⋅251⁸ ≡ 53⋅53=2809 ≡ 223 mod 431

32: 251³²=251¹⁶⁺¹⁶=251¹⁶⋅251¹⁶ ≡ 223⋅223=49729 ≡ 164 mod 431

64: 251⁶⁴=251³²⁺³²=251³²⋅251³² ≡ 164⋅164=26896 ≡ 174 mod 431

128: 251¹²⁸=251⁶⁴⁺⁶⁴=251⁶⁴⋅251⁶⁴ ≡ 174⋅174=30276 ≡ 106 mod 431

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

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

248 = 128+64+32+16+8

134²⁴⁸

= 134^{128+64+32+16+8}

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

≡ 135 ⋅ 52 ⋅ 137 ⋅ 258 ⋅ 25 mod 367
≡ 7020 ⋅ 137 ⋅ 258 ⋅ 25 mod 367 ≡ 47 ⋅ 137 ⋅ 258 ⋅ 25 mod 367
≡ 6439 ⋅ 258 ⋅ 25 mod 367 ≡ 200 ⋅ 258 ⋅ 25 mod 367
≡ 51600 ⋅ 25 mod 367 ≡ 220 ⋅ 25 mod 367
≡ 5500 mod 367 ≡ 362 mod 367

Es gilt also: 134²⁴⁸ ≡ 362 mod 367

Berechnung des größten gemeinsamen Teilers von 67 und 40

=>67	= 1⋅40 + 27
=>40	= 1⋅27 + 13
=>27	= 2⋅13 + 1
=>13	= 13⋅1 + 0

also gilt: ggt(67,40)=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= 27-2⋅13
13= 40-1⋅27	eingesetzt in die Zeile drüber:	1	= 1⋅27 -2⋅(40 -1⋅ 27) = 1⋅27 -2⋅40 +2⋅ 27) = -2⋅40 +3⋅ 27 (=1)
27= 67-1⋅40	eingesetzt in die Zeile drüber:	1	= -2⋅40 +3⋅(67 -1⋅ 40) = -2⋅40 +3⋅67 -3⋅ 40) = 3⋅67 -5⋅ 40 (=1)

Es gilt also: ggt(67,40)=1 = 3⋅67 -5⋅40

oder wenn man 3⋅67 auf die linke Seite bringt:

1 -3⋅67 = -5⋅40

-5⋅40 = -3⋅67 + 1 |+67⋅40

-5⋅40 + 67⋅40 = -3⋅67 + 67⋅40 + 1

(-5 + 67) ⋅ 40 = (-3 + 40) ⋅ 67 + 1

62⋅40 = 37⋅67 + 1

Es gilt also: 62⋅40 = 37⋅67 +1

Somit 62⋅40 = 1 mod 67

62 ist also das Inverse von 40 mod 67