Um längere Rechnungen zu vermeiden, rechnen wir:

(235 + 326) mod 8 ≡ (235 mod 8 + 326 mod 8) mod 8.

235 mod 8 ≡ 3 mod 8 kann man relativ leicht bestimmen, weil ja 235 = 240-5 = 8 ⋅ 30 -5 = 8 ⋅ 30 - 8 + 3.

326 mod 8 ≡ 6 mod 8 kann man relativ leicht bestimmen, weil ja 326 = 320+6 = 8 ⋅ 40 +6.

Somit gilt:

(235 + 326) mod 8 ≡ (3 + 6) mod 8 ≡ 9 mod 8 ≡ 1 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(53 ⋅ 19) mod 5 ≡ (53 mod 5 ⋅ 19 mod 5) mod 5.

53 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 53 = 50 + 3 = 10 ⋅ 5 + 3 ist.

19 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 19 = 15 + 4 = 3 ⋅ 5 + 4 ist.

Somit gilt:

(53 ⋅ 19) mod 5 ≡ (3 ⋅ 4) mod 5 ≡ 12 mod 5 ≡ 2 mod 5.

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

2: 136²=136¹⁺¹=136¹⋅136¹ ≡ 136⋅136=18496 ≡ 58 mod 439

4: 136⁴=136²⁺²=136²⋅136² ≡ 58⋅58=3364 ≡ 291 mod 439

8: 136⁸=136⁴⁺⁴=136⁴⋅136⁴ ≡ 291⋅291=84681 ≡ 393 mod 439

16: 136¹⁶=136⁸⁺⁸=136⁸⋅136⁸ ≡ 393⋅393=154449 ≡ 360 mod 439

32: 136³²=136¹⁶⁺¹⁶=136¹⁶⋅136¹⁶ ≡ 360⋅360=129600 ≡ 95 mod 439

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

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

93 = 64+16+8+4+1

527⁹³

= 527^64+16+8+4+1

= 527⁶⁴⋅527¹⁶⋅527⁸⋅527⁴⋅527¹

≡ 13 ⋅ 165 ⋅ 349 ⋅ 382 ⋅ 527 mod 647
≡ 2145 ⋅ 349 ⋅ 382 ⋅ 527 mod 647 ≡ 204 ⋅ 349 ⋅ 382 ⋅ 527 mod 647
≡ 71196 ⋅ 382 ⋅ 527 mod 647 ≡ 26 ⋅ 382 ⋅ 527 mod 647
≡ 9932 ⋅ 527 mod 647 ≡ 227 ⋅ 527 mod 647
≡ 119629 mod 647 ≡ 581 mod 647

Es gilt also: 527⁹³ ≡ 581 mod 647

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

=>89	= 2⋅42 + 5
=>42	= 8⋅5 + 2
=>5	= 2⋅2 + 1
=>2	= 2⋅1 + 0

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

Es gilt also: ggt(89,42)=1 = 17⋅89 -36⋅42

oder wenn man 17⋅89 auf die linke Seite bringt:

1 -17⋅89 = -36⋅42

-36⋅42 = -17⋅89 + 1 |+89⋅42

-36⋅42 + 89⋅42 = -17⋅89 + 89⋅42 + 1

(-36 + 89) ⋅ 42 = (-17 + 42) ⋅ 89 + 1

53⋅42 = 25⋅89 + 1

Es gilt also: 53⋅42 = 25⋅89 +1

Somit 53⋅42 = 1 mod 89

53 ist also das Inverse von 42 mod 89