Um längere Rechnungen zu vermeiden, rechnen wir:

(167 - 8005) mod 8 ≡ (167 mod 8 - 8005 mod 8) mod 8.

167 mod 8 ≡ 7 mod 8 kann man relativ leicht bestimmen, weil ja 167 = 160+7 = 8 ⋅ 20 +7.

8005 mod 8 ≡ 5 mod 8 kann man relativ leicht bestimmen, weil ja 8005 = 8000+5 = 8 ⋅ 1000 +5.

Somit gilt:

(167 - 8005) mod 8 ≡ (7 - 5) mod 8 ≡ 2 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(100 ⋅ 49) mod 11 ≡ (100 mod 11 ⋅ 49 mod 11) mod 11.

100 mod 11 ≡ 1 mod 11 kann man relativ leicht bestimmen, weil ja 100 = 99 + 1 = 9 ⋅ 11 + 1 ist.

49 mod 11 ≡ 5 mod 11 kann man relativ leicht bestimmen, weil ja 49 = 44 + 5 = 4 ⋅ 11 + 5 ist.

Somit gilt:

(100 ⋅ 49) mod 11 ≡ (1 ⋅ 5) mod 11 ≡ 5 mod 11.

Die 16 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: 642¹=642

2: 642²=642¹⁺¹=642¹⋅642¹ ≡ 642⋅642=412164 ≡ 25 mod 647

4: 642⁴=642²⁺²=642²⋅642² ≡ 25⋅25=625 ≡ 625 mod 647

8: 642⁸=642⁴⁺⁴=642⁴⋅642⁴ ≡ 625⋅625=390625 ≡ 484 mod 647

16: 642¹⁶=642⁸⁺⁸=642⁸⋅642⁸ ≡ 484⋅484=234256 ≡ 42 mod 647

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

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

253 = 128+64+32+16+8+4+1

431²⁵³

= 431^{128+64+32+16+8+4+1}

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

≡ 477 ⋅ 515 ⋅ 213 ⋅ 49 ⋅ 540 ⋅ 372 ⋅ 431 mod 547
≡ 245655 ⋅ 213 ⋅ 49 ⋅ 540 ⋅ 372 ⋅ 431 mod 547 ≡ 52 ⋅ 213 ⋅ 49 ⋅ 540 ⋅ 372 ⋅ 431 mod 547
≡ 11076 ⋅ 49 ⋅ 540 ⋅ 372 ⋅ 431 mod 547 ≡ 136 ⋅ 49 ⋅ 540 ⋅ 372 ⋅ 431 mod 547
≡ 6664 ⋅ 540 ⋅ 372 ⋅ 431 mod 547 ≡ 100 ⋅ 540 ⋅ 372 ⋅ 431 mod 547
≡ 54000 ⋅ 372 ⋅ 431 mod 547 ≡ 394 ⋅ 372 ⋅ 431 mod 547
≡ 146568 ⋅ 431 mod 547 ≡ 519 ⋅ 431 mod 547
≡ 223689 mod 547 ≡ 513 mod 547

Es gilt also: 431²⁵³ ≡ 513 mod 547

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

=>67	= 1⋅42 + 25
=>42	= 1⋅25 + 17
=>25	= 1⋅17 + 8
=>17	= 2⋅8 + 1
=>8	= 8⋅1 + 0

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

Es gilt also: ggt(67,42)=1 = -5⋅67 +8⋅42

oder wenn man -5⋅67 auf die linke Seite bringt:

1 +5⋅67 = +8⋅42

Es gilt also: 8⋅42 = 5⋅67 +1

Somit 8⋅42 = 1 mod 67

8 ist also das Inverse von 42 mod 67