Um längere Rechnungen zu vermeiden, rechnen wir:

(183 + 2706) mod 9 ≡ (183 mod 9 + 2706 mod 9) mod 9.

183 mod 9 ≡ 3 mod 9 kann man relativ leicht bestimmen, weil ja 183 = 180+3 = 9 ⋅ 20 +3.

2706 mod 9 ≡ 6 mod 9 kann man relativ leicht bestimmen, weil ja 2706 = 2700+6 = 9 ⋅ 300 +6.

Somit gilt:

(183 + 2706) mod 9 ≡ (3 + 6) mod 9 ≡ 9 mod 9 ≡ 0 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(52 ⋅ 99) mod 4 ≡ (52 mod 4 ⋅ 99 mod 4) mod 4.

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

99 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 99 = 96 + 3 = 24 ⋅ 4 + 3 ist.

Somit gilt:

(52 ⋅ 99) mod 4 ≡ (0 ⋅ 3) mod 4 ≡ 0 mod 4.

Die 32 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: 209¹=209

2: 209²=209¹⁺¹=209¹⋅209¹ ≡ 209⋅209=43681 ≡ 187 mod 659

4: 209⁴=209²⁺²=209²⋅209² ≡ 187⋅187=34969 ≡ 42 mod 659

8: 209⁸=209⁴⁺⁴=209⁴⋅209⁴ ≡ 42⋅42=1764 ≡ 446 mod 659

16: 209¹⁶=209⁸⁺⁸=209⁸⋅209⁸ ≡ 446⋅446=198916 ≡ 557 mod 659

32: 209³²=209¹⁶⁺¹⁶=209¹⁶⋅209¹⁶ ≡ 557⋅557=310249 ≡ 519 mod 659

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

337²²³

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

= 337¹²⁸⋅337⁶⁴⋅337¹⁶⋅337⁸⋅337⁴⋅337²⋅337¹

≡ 285 ⋅ 485 ⋅ 562 ⋅ 172 ⋅ 599 ⋅ 245 ⋅ 337 mod 691
≡ 138225 ⋅ 562 ⋅ 172 ⋅ 599 ⋅ 245 ⋅ 337 mod 691 ≡ 25 ⋅ 562 ⋅ 172 ⋅ 599 ⋅ 245 ⋅ 337 mod 691
≡ 14050 ⋅ 172 ⋅ 599 ⋅ 245 ⋅ 337 mod 691 ≡ 230 ⋅ 172 ⋅ 599 ⋅ 245 ⋅ 337 mod 691
≡ 39560 ⋅ 599 ⋅ 245 ⋅ 337 mod 691 ≡ 173 ⋅ 599 ⋅ 245 ⋅ 337 mod 691
≡ 103627 ⋅ 245 ⋅ 337 mod 691 ≡ 668 ⋅ 245 ⋅ 337 mod 691
≡ 163660 ⋅ 337 mod 691 ≡ 584 ⋅ 337 mod 691
≡ 196808 mod 691 ≡ 564 mod 691

Es gilt also: 337²²³ ≡ 564 mod 691

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

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

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

Es gilt also: ggt(79,24)=1 = 7⋅79 -23⋅24

oder wenn man 7⋅79 auf die linke Seite bringt:

1 -7⋅79 = -23⋅24

-23⋅24 = -7⋅79 + 1 |+79⋅24

-23⋅24 + 79⋅24 = -7⋅79 + 79⋅24 + 1

(-23 + 79) ⋅ 24 = (-7 + 24) ⋅ 79 + 1

56⋅24 = 17⋅79 + 1

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

Somit 56⋅24 = 1 mod 79

56 ist also das Inverse von 24 mod 79