Um längere Rechnungen zu vermeiden, rechnen wir:

(84 + 270) mod 9 ≡ (84 mod 9 + 270 mod 9) mod 9.

84 mod 9 ≡ 3 mod 9 kann man relativ leicht bestimmen, weil ja 84 = 90-6 = 9 ⋅ 10 -6 = 9 ⋅ 10 - 9 + 3.

270 mod 9 ≡ 0 mod 9 kann man relativ leicht bestimmen, weil ja 270 = 270+0 = 9 ⋅ 30 +0.

Somit gilt:

(84 + 270) mod 9 ≡ (3 + 0) mod 9 ≡ 3 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(81 ⋅ 86) mod 6 ≡ (81 mod 6 ⋅ 86 mod 6) mod 6.

81 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 81 = 78 + 3 = 13 ⋅ 6 + 3 ist.

86 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 86 = 84 + 2 = 14 ⋅ 6 + 2 ist.

Somit gilt:

(81 ⋅ 86) mod 6 ≡ (3 ⋅ 2) mod 6 ≡ 6 mod 6 ≡ 0 mod 6.

Die 8 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: 541¹=541

2: 541²=541¹⁺¹=541¹⋅541¹ ≡ 541⋅541=292681 ≡ 256 mod 557

4: 541⁴=541²⁺²=541²⋅541² ≡ 256⋅256=65536 ≡ 367 mod 557

8: 541⁸=541⁴⁺⁴=541⁴⋅541⁴ ≡ 367⋅367=134689 ≡ 452 mod 557

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

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

254 = 128+64+32+16+8+4+2

94²⁵⁴

= 94^{128+64+32+16+8+4+2}

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

≡ 256 ⋅ 241 ⋅ 193 ⋅ 129 ⋅ 30 ⋅ 95 ⋅ 98 mod 257
≡ 61696 ⋅ 193 ⋅ 129 ⋅ 30 ⋅ 95 ⋅ 98 mod 257 ≡ 16 ⋅ 193 ⋅ 129 ⋅ 30 ⋅ 95 ⋅ 98 mod 257
≡ 3088 ⋅ 129 ⋅ 30 ⋅ 95 ⋅ 98 mod 257 ≡ 4 ⋅ 129 ⋅ 30 ⋅ 95 ⋅ 98 mod 257
≡ 516 ⋅ 30 ⋅ 95 ⋅ 98 mod 257 ≡ 2 ⋅ 30 ⋅ 95 ⋅ 98 mod 257
≡ 60 ⋅ 95 ⋅ 98 mod 257
≡ 5700 ⋅ 98 mod 257 ≡ 46 ⋅ 98 mod 257
≡ 4508 mod 257 ≡ 139 mod 257

Es gilt also: 94²⁵⁴ ≡ 139 mod 257

Berechnung des größten gemeinsamen Teilers von 71 und 49

=>71	= 1⋅49 + 22
=>49	= 2⋅22 + 5
=>22	= 4⋅5 + 2
=>5	= 2⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(71,49)=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= 22-4⋅5	eingesetzt in die Zeile drüber:	1	= 1⋅5 -2⋅(22 -4⋅ 5) = 1⋅5 -2⋅22 +8⋅ 5) = -2⋅22 +9⋅ 5 (=1)
5= 49-2⋅22	eingesetzt in die Zeile drüber:	1	= -2⋅22 +9⋅(49 -2⋅ 22) = -2⋅22 +9⋅49 -18⋅ 22) = 9⋅49 -20⋅ 22 (=1)
22= 71-1⋅49	eingesetzt in die Zeile drüber:	1	= 9⋅49 -20⋅(71 -1⋅ 49) = 9⋅49 -20⋅71 +20⋅ 49) = -20⋅71 +29⋅ 49 (=1)

Es gilt also: ggt(71,49)=1 = -20⋅71 +29⋅49

oder wenn man -20⋅71 auf die linke Seite bringt:

1 +20⋅71 = +29⋅49

Es gilt also: 29⋅49 = 20⋅71 +1

Somit 29⋅49 = 1 mod 71

29 ist also das Inverse von 49 mod 71