Um längere Rechnungen zu vermeiden, rechnen wir:

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

16003 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 16003 = 16000+3 = 4 ⋅ 4000 +3.

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

Somit gilt:

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

Um längere Rechnungen zu vermeiden, rechnen wir:

(53 ⋅ 73) mod 6 ≡ (53 mod 6 ⋅ 73 mod 6) mod 6.

53 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 53 = 48 + 5 = 8 ⋅ 6 + 5 ist.

73 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 73 = 72 + 1 = 12 ⋅ 6 + 1 ist.

Somit gilt:

(53 ⋅ 73) mod 6 ≡ (5 ⋅ 1) mod 6 ≡ 5 mod 6.

Die 128 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: 241¹=241

2: 241²=241¹⁺¹=241¹⋅241¹ ≡ 241⋅241=58081 ≡ 381 mod 577

4: 241⁴=241²⁺²=241²⋅241² ≡ 381⋅381=145161 ≡ 334 mod 577

8: 241⁸=241⁴⁺⁴=241⁴⋅241⁴ ≡ 334⋅334=111556 ≡ 195 mod 577

16: 241¹⁶=241⁸⁺⁸=241⁸⋅241⁸ ≡ 195⋅195=38025 ≡ 520 mod 577

32: 241³²=241¹⁶⁺¹⁶=241¹⁶⋅241¹⁶ ≡ 520⋅520=270400 ≡ 364 mod 577

64: 241⁶⁴=241³²⁺³²=241³²⋅241³² ≡ 364⋅364=132496 ≡ 363 mod 577

128: 241¹²⁸=241⁶⁴⁺⁶⁴=241⁶⁴⋅241⁶⁴ ≡ 363⋅363=131769 ≡ 213 mod 577

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

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

92 = 64+16+8+4

187⁹²

= 187^64+16+8+4

= 187⁶⁴⋅187¹⁶⋅187⁸⋅187⁴

≡ 1 ⋅ 1 ⋅ 1 ⋅ 1 mod 269
≡ 1 ⋅ 1 ⋅ 1 mod 269
≡ 1 ⋅ 1 mod 269
≡ 1 mod 269

Es gilt also: 187⁹² ≡ 1 mod 269

Berechnung des größten gemeinsamen Teilers von 79 und 56

=>79	= 1⋅56 + 23
=>56	= 2⋅23 + 10
=>23	= 2⋅10 + 3
=>10	= 3⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(79,56)=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= 10-3⋅3
3= 23-2⋅10	eingesetzt in die Zeile drüber:	1	= 1⋅10 -3⋅(23 -2⋅ 10) = 1⋅10 -3⋅23 +6⋅ 10) = -3⋅23 +7⋅ 10 (=1)
10= 56-2⋅23	eingesetzt in die Zeile drüber:	1	= -3⋅23 +7⋅(56 -2⋅ 23) = -3⋅23 +7⋅56 -14⋅ 23) = 7⋅56 -17⋅ 23 (=1)
23= 79-1⋅56	eingesetzt in die Zeile drüber:	1	= 7⋅56 -17⋅(79 -1⋅ 56) = 7⋅56 -17⋅79 +17⋅ 56) = -17⋅79 +24⋅ 56 (=1)

Es gilt also: ggt(79,56)=1 = -17⋅79 +24⋅56

oder wenn man -17⋅79 auf die linke Seite bringt:

1 +17⋅79 = +24⋅56

Es gilt also: 24⋅56 = 17⋅79 +1

Somit 24⋅56 = 1 mod 79

24 ist also das Inverse von 56 mod 79