Um längere Rechnungen zu vermeiden, rechnen wir:

(11999 - 200) mod 4 ≡ (11999 mod 4 - 200 mod 4) mod 4.

11999 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 11999 = 11000+999 = 4 ⋅ 2750 +999.

200 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 200 = 200+0 = 4 ⋅ 50 +0.

Somit gilt:

(11999 - 200) mod 4 ≡ (3 - 0) mod 4 ≡ 3 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(23 ⋅ 94) mod 3 ≡ (23 mod 3 ⋅ 94 mod 3) mod 3.

23 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 23 = 21 + 2 = 7 ⋅ 3 + 2 ist.

94 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 94 = 93 + 1 = 31 ⋅ 3 + 1 ist.

Somit gilt:

(23 ⋅ 94) mod 3 ≡ (2 ⋅ 1) mod 3 ≡ 2 mod 3.

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

2: 163²=163¹⁺¹=163¹⋅163¹ ≡ 163⋅163=26569 ≡ 214 mod 251

4: 163⁴=163²⁺²=163²⋅163² ≡ 214⋅214=45796 ≡ 114 mod 251

8: 163⁸=163⁴⁺⁴=163⁴⋅163⁴ ≡ 114⋅114=12996 ≡ 195 mod 251

16: 163¹⁶=163⁸⁺⁸=163⁸⋅163⁸ ≡ 195⋅195=38025 ≡ 124 mod 251

32: 163³²=163¹⁶⁺¹⁶=163¹⁶⋅163¹⁶ ≡ 124⋅124=15376 ≡ 65 mod 251

64: 163⁶⁴=163³²⁺³²=163³²⋅163³² ≡ 65⋅65=4225 ≡ 209 mod 251

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

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

151 = 128+16+4+2+1

238¹⁵¹

= 238^128+16+4+2+1

= 238¹²⁸⋅238¹⁶⋅238⁴⋅238²⋅238¹

≡ 602 ⋅ 168 ⋅ 77 ⋅ 330 ⋅ 238 mod 761
≡ 101136 ⋅ 77 ⋅ 330 ⋅ 238 mod 761 ≡ 684 ⋅ 77 ⋅ 330 ⋅ 238 mod 761
≡ 52668 ⋅ 330 ⋅ 238 mod 761 ≡ 159 ⋅ 330 ⋅ 238 mod 761
≡ 52470 ⋅ 238 mod 761 ≡ 722 ⋅ 238 mod 761
≡ 171836 mod 761 ≡ 611 mod 761

Es gilt also: 238¹⁵¹ ≡ 611 mod 761

Berechnung des größten gemeinsamen Teilers von 97 und 64

=>97	= 1⋅64 + 33
=>64	= 1⋅33 + 31
=>33	= 1⋅31 + 2
=>31	= 15⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(97,64)=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= 31-15⋅2
2= 33-1⋅31	eingesetzt in die Zeile drüber:	1	= 1⋅31 -15⋅(33 -1⋅ 31) = 1⋅31 -15⋅33 +15⋅ 31) = -15⋅33 +16⋅ 31 (=1)
31= 64-1⋅33	eingesetzt in die Zeile drüber:	1	= -15⋅33 +16⋅(64 -1⋅ 33) = -15⋅33 +16⋅64 -16⋅ 33) = 16⋅64 -31⋅ 33 (=1)
33= 97-1⋅64	eingesetzt in die Zeile drüber:	1	= 16⋅64 -31⋅(97 -1⋅ 64) = 16⋅64 -31⋅97 +31⋅ 64) = -31⋅97 +47⋅ 64 (=1)

Es gilt also: ggt(97,64)=1 = -31⋅97 +47⋅64

oder wenn man -31⋅97 auf die linke Seite bringt:

1 +31⋅97 = +47⋅64

Es gilt also: 47⋅64 = 31⋅97 +1

Somit 47⋅64 = 1 mod 97

47 ist also das Inverse von 64 mod 97