Um längere Rechnungen zu vermeiden, rechnen wir:

(117 - 1196) mod 4 ≡ (117 mod 4 - 1196 mod 4) mod 4.

117 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 117 = 120-3 = 4 ⋅ 30 -3 = 4 ⋅ 30 - 4 + 1.

1196 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 1196 = 1100+96 = 4 ⋅ 275 +96.

Somit gilt:

(117 - 1196) mod 4 ≡ (1 - 0) mod 4 ≡ 1 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(60 ⋅ 84) mod 9 ≡ (60 mod 9 ⋅ 84 mod 9) mod 9.

60 mod 9 ≡ 6 mod 9 kann man relativ leicht bestimmen, weil ja 60 = 54 + 6 = 6 ⋅ 9 + 6 ist.

84 mod 9 ≡ 3 mod 9 kann man relativ leicht bestimmen, weil ja 84 = 81 + 3 = 9 ⋅ 9 + 3 ist.

Somit gilt:

(60 ⋅ 84) mod 9 ≡ (6 ⋅ 3) mod 9 ≡ 18 mod 9 ≡ 0 mod 9.

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

2: 431²=431¹⁺¹=431¹⋅431¹ ≡ 431⋅431=185761 ≡ 65 mod 829

4: 431⁴=431²⁺²=431²⋅431² ≡ 65⋅65=4225 ≡ 80 mod 829

8: 431⁸=431⁴⁺⁴=431⁴⋅431⁴ ≡ 80⋅80=6400 ≡ 597 mod 829

16: 431¹⁶=431⁸⁺⁸=431⁸⋅431⁸ ≡ 597⋅597=356409 ≡ 768 mod 829

32: 431³²=431¹⁶⁺¹⁶=431¹⁶⋅431¹⁶ ≡ 768⋅768=589824 ≡ 405 mod 829

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

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

221 = 128+64+16+8+4+1

626²²¹

= 626^{128+64+16+8+4+1}

= 626¹²⁸⋅626⁶⁴⋅626¹⁶⋅626⁸⋅626⁴⋅626¹

≡ 794 ⋅ 846 ⋅ 127 ⋅ 301 ⋅ 639 ⋅ 626 mod 887
≡ 671724 ⋅ 127 ⋅ 301 ⋅ 639 ⋅ 626 mod 887 ≡ 265 ⋅ 127 ⋅ 301 ⋅ 639 ⋅ 626 mod 887
≡ 33655 ⋅ 301 ⋅ 639 ⋅ 626 mod 887 ≡ 836 ⋅ 301 ⋅ 639 ⋅ 626 mod 887
≡ 251636 ⋅ 639 ⋅ 626 mod 887 ≡ 615 ⋅ 639 ⋅ 626 mod 887
≡ 392985 ⋅ 626 mod 887 ≡ 44 ⋅ 626 mod 887
≡ 27544 mod 887 ≡ 47 mod 887

Es gilt also: 626²²¹ ≡ 47 mod 887

Berechnung des größten gemeinsamen Teilers von 83 und 30

=>83	= 2⋅30 + 23
=>30	= 1⋅23 + 7
=>23	= 3⋅7 + 2
=>7	= 3⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(83,30)=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= 7-3⋅2
2= 23-3⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -3⋅(23 -3⋅ 7) = 1⋅7 -3⋅23 +9⋅ 7) = -3⋅23 +10⋅ 7 (=1)
7= 30-1⋅23	eingesetzt in die Zeile drüber:	1	= -3⋅23 +10⋅(30 -1⋅ 23) = -3⋅23 +10⋅30 -10⋅ 23) = 10⋅30 -13⋅ 23 (=1)
23= 83-2⋅30	eingesetzt in die Zeile drüber:	1	= 10⋅30 -13⋅(83 -2⋅ 30) = 10⋅30 -13⋅83 +26⋅ 30) = -13⋅83 +36⋅ 30 (=1)

Es gilt also: ggt(83,30)=1 = -13⋅83 +36⋅30

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

1 +13⋅83 = +36⋅30

Es gilt also: 36⋅30 = 13⋅83 +1

Somit 36⋅30 = 1 mod 83

36 ist also das Inverse von 30 mod 83