Um längere Rechnungen zu vermeiden, rechnen wir:

(303 + 30) mod 3 ≡ (303 mod 3 + 30 mod 3) mod 3.

303 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 303 = 300+3 = 3 ⋅ 100 +3.

30 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 30 = 30+0 = 3 ⋅ 10 +0.

Somit gilt:

(303 + 30) mod 3 ≡ (0 + 0) mod 3 ≡ 0 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(55 ⋅ 53) mod 4 ≡ (55 mod 4 ⋅ 53 mod 4) mod 4.

55 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 55 = 52 + 3 = 13 ⋅ 4 + 3 ist.

53 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 53 = 52 + 1 = 13 ⋅ 4 + 1 ist.

Somit gilt:

(55 ⋅ 53) mod 4 ≡ (3 ⋅ 1) mod 4 ≡ 3 mod 4.

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

2: 249²=249¹⁺¹=249¹⋅249¹ ≡ 249⋅249=62001 ≡ 294 mod 307

4: 249⁴=249²⁺²=249²⋅249² ≡ 294⋅294=86436 ≡ 169 mod 307

8: 249⁸=249⁴⁺⁴=249⁴⋅249⁴ ≡ 169⋅169=28561 ≡ 10 mod 307

16: 249¹⁶=249⁸⁺⁸=249⁸⋅249⁸ ≡ 10⋅10=100 ≡ 100 mod 307

32: 249³²=249¹⁶⁺¹⁶=249¹⁶⋅249¹⁶ ≡ 100⋅100=10000 ≡ 176 mod 307

64: 249⁶⁴=249³²⁺³²=249³²⋅249³² ≡ 176⋅176=30976 ≡ 276 mod 307

128: 249¹²⁸=249⁶⁴⁺⁶⁴=249⁶⁴⋅249⁶⁴ ≡ 276⋅276=76176 ≡ 40 mod 307

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

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

223 = 128+64+16+8+4+2+1

659²²³

= 659^{128+64+16+8+4+2+1}

= 659¹²⁸⋅659⁶⁴⋅659¹⁶⋅659⁸⋅659⁴⋅659²⋅659¹

≡ 610 ⋅ 680 ⋅ 658 ⋅ 143 ⋅ 279 ⋅ 345 ⋅ 659 mod 733
≡ 414800 ⋅ 658 ⋅ 143 ⋅ 279 ⋅ 345 ⋅ 659 mod 733 ≡ 655 ⋅ 658 ⋅ 143 ⋅ 279 ⋅ 345 ⋅ 659 mod 733
≡ 430990 ⋅ 143 ⋅ 279 ⋅ 345 ⋅ 659 mod 733 ≡ 719 ⋅ 143 ⋅ 279 ⋅ 345 ⋅ 659 mod 733
≡ 102817 ⋅ 279 ⋅ 345 ⋅ 659 mod 733 ≡ 197 ⋅ 279 ⋅ 345 ⋅ 659 mod 733
≡ 54963 ⋅ 345 ⋅ 659 mod 733 ≡ 721 ⋅ 345 ⋅ 659 mod 733
≡ 248745 ⋅ 659 mod 733 ≡ 258 ⋅ 659 mod 733
≡ 170022 mod 733 ≡ 699 mod 733

Es gilt also: 659²²³ ≡ 699 mod 733

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

=>79	= 1⋅55 + 24
=>55	= 2⋅24 + 7
=>24	= 3⋅7 + 3
=>7	= 2⋅3 + 1
=>3	= 3⋅1 + 0

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

Es gilt also: ggt(79,55)=1 = -16⋅79 +23⋅55

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

1 +16⋅79 = +23⋅55

Es gilt also: 23⋅55 = 16⋅79 +1

Somit 23⋅55 = 1 mod 79

23 ist also das Inverse von 55 mod 79