Um längere Rechnungen zu vermeiden, rechnen wir:

(447 + 897) mod 9 ≡ (447 mod 9 + 897 mod 9) mod 9.

447 mod 9 ≡ 6 mod 9 kann man relativ leicht bestimmen, weil ja 447 = 450-3 = 9 ⋅ 50 -3 = 9 ⋅ 50 - 9 + 6.

897 mod 9 ≡ 6 mod 9 kann man relativ leicht bestimmen, weil ja 897 = 900-3 = 9 ⋅ 100 -3 = 9 ⋅ 100 - 9 + 6.

Somit gilt:

(447 + 897) mod 9 ≡ (6 + 6) mod 9 ≡ 12 mod 9 ≡ 3 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

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

32 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 32 = 30 + 2 = 6 ⋅ 5 + 2 ist.

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

Somit gilt:

(32 ⋅ 36) mod 5 ≡ (2 ⋅ 1) mod 5 ≡ 2 mod 5.

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

2: 714²=714¹⁺¹=714¹⋅714¹ ≡ 714⋅714=509796 ≡ 359 mod 823

4: 714⁴=714²⁺²=714²⋅714² ≡ 359⋅359=128881 ≡ 493 mod 823

8: 714⁸=714⁴⁺⁴=714⁴⋅714⁴ ≡ 493⋅493=243049 ≡ 264 mod 823

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

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

243 = 128+64+32+16+2+1

384²⁴³

= 384^{128+64+32+16+2+1}

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

≡ 170 ⋅ 234 ⋅ 248 ⋅ 185 ⋅ 408 ⋅ 384 mod 557
≡ 39780 ⋅ 248 ⋅ 185 ⋅ 408 ⋅ 384 mod 557 ≡ 233 ⋅ 248 ⋅ 185 ⋅ 408 ⋅ 384 mod 557
≡ 57784 ⋅ 185 ⋅ 408 ⋅ 384 mod 557 ≡ 413 ⋅ 185 ⋅ 408 ⋅ 384 mod 557
≡ 76405 ⋅ 408 ⋅ 384 mod 557 ≡ 96 ⋅ 408 ⋅ 384 mod 557
≡ 39168 ⋅ 384 mod 557 ≡ 178 ⋅ 384 mod 557
≡ 68352 mod 557 ≡ 398 mod 557

Es gilt also: 384²⁴³ ≡ 398 mod 557

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

=>71	= 2⋅28 + 15
=>28	= 1⋅15 + 13
=>15	= 1⋅13 + 2
=>13	= 6⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(71,28)=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-6⋅2
2= 15-1⋅13	eingesetzt in die Zeile drüber:	1	= 1⋅13 -6⋅(15 -1⋅ 13) = 1⋅13 -6⋅15 +6⋅ 13) = -6⋅15 +7⋅ 13 (=1)
13= 28-1⋅15	eingesetzt in die Zeile drüber:	1	= -6⋅15 +7⋅(28 -1⋅ 15) = -6⋅15 +7⋅28 -7⋅ 15) = 7⋅28 -13⋅ 15 (=1)
15= 71-2⋅28	eingesetzt in die Zeile drüber:	1	= 7⋅28 -13⋅(71 -2⋅ 28) = 7⋅28 -13⋅71 +26⋅ 28) = -13⋅71 +33⋅ 28 (=1)

Es gilt also: ggt(71,28)=1 = -13⋅71 +33⋅28

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

1 +13⋅71 = +33⋅28

Es gilt also: 33⋅28 = 13⋅71 +1

Somit 33⋅28 = 1 mod 71

33 ist also das Inverse von 28 mod 71