Um längere Rechnungen zu vermeiden, rechnen wir:

(3206 - 15996) mod 8 ≡ (3206 mod 8 - 15996 mod 8) mod 8.

3206 mod 8 ≡ 6 mod 8 kann man relativ leicht bestimmen, weil ja 3206 = 3200+6 = 8 ⋅ 400 +6.

15996 mod 8 ≡ 4 mod 8 kann man relativ leicht bestimmen, weil ja 15996 = 15000+996 = 8 ⋅ 1875 +996.

Somit gilt:

(3206 - 15996) mod 8 ≡ (6 - 4) mod 8 ≡ 2 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(53 ⋅ 16) mod 7 ≡ (53 mod 7 ⋅ 16 mod 7) mod 7.

53 mod 7 ≡ 4 mod 7 kann man relativ leicht bestimmen, weil ja 53 = 49 + 4 = 7 ⋅ 7 + 4 ist.

16 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 16 = 14 + 2 = 2 ⋅ 7 + 2 ist.

Somit gilt:

(53 ⋅ 16) mod 7 ≡ (4 ⋅ 2) mod 7 ≡ 8 mod 7 ≡ 1 mod 7.

Die 64 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: 561¹=561

2: 561²=561¹⁺¹=561¹⋅561¹ ≡ 561⋅561=314721 ≡ 446 mod 967

4: 561⁴=561²⁺²=561²⋅561² ≡ 446⋅446=198916 ≡ 681 mod 967

8: 561⁸=561⁴⁺⁴=561⁴⋅561⁴ ≡ 681⋅681=463761 ≡ 568 mod 967

16: 561¹⁶=561⁸⁺⁸=561⁸⋅561⁸ ≡ 568⋅568=322624 ≡ 613 mod 967

32: 561³²=561¹⁶⁺¹⁶=561¹⁶⋅561¹⁶ ≡ 613⋅613=375769 ≡ 573 mod 967

64: 561⁶⁴=561³²⁺³²=561³²⋅561³² ≡ 573⋅573=328329 ≡ 516 mod 967

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

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

234 = 128+64+32+8+2

329²³⁴

= 329^{128+64+32+8+2}

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

≡ 114 ⋅ 144 ⋅ 12 ⋅ 305 ⋅ 221 mod 491
≡ 16416 ⋅ 12 ⋅ 305 ⋅ 221 mod 491 ≡ 213 ⋅ 12 ⋅ 305 ⋅ 221 mod 491
≡ 2556 ⋅ 305 ⋅ 221 mod 491 ≡ 101 ⋅ 305 ⋅ 221 mod 491
≡ 30805 ⋅ 221 mod 491 ≡ 363 ⋅ 221 mod 491
≡ 80223 mod 491 ≡ 190 mod 491

Es gilt also: 329²³⁴ ≡ 190 mod 491

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

=>67	= 1⋅58 + 9
=>58	= 6⋅9 + 4
=>9	= 2⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(67,58)=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= 9-2⋅4
4= 58-6⋅9	eingesetzt in die Zeile drüber:	1	= 1⋅9 -2⋅(58 -6⋅ 9) = 1⋅9 -2⋅58 +12⋅ 9) = -2⋅58 +13⋅ 9 (=1)
9= 67-1⋅58	eingesetzt in die Zeile drüber:	1	= -2⋅58 +13⋅(67 -1⋅ 58) = -2⋅58 +13⋅67 -13⋅ 58) = 13⋅67 -15⋅ 58 (=1)

Es gilt also: ggt(67,58)=1 = 13⋅67 -15⋅58

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

1 -13⋅67 = -15⋅58

-15⋅58 = -13⋅67 + 1 |+67⋅58

-15⋅58 + 67⋅58 = -13⋅67 + 67⋅58 + 1

(-15 + 67) ⋅ 58 = (-13 + 58) ⋅ 67 + 1

52⋅58 = 45⋅67 + 1

Es gilt also: 52⋅58 = 45⋅67 +1

Somit 52⋅58 = 1 mod 67

52 ist also das Inverse von 58 mod 67