Um längere Rechnungen zu vermeiden, rechnen wir:

(907 + 3594) mod 9 ≡ (907 mod 9 + 3594 mod 9) mod 9.

907 mod 9 ≡ 7 mod 9 kann man relativ leicht bestimmen, weil ja 907 = 900+7 = 9 ⋅ 100 +7.

3594 mod 9 ≡ 3 mod 9 kann man relativ leicht bestimmen, weil ja 3594 = 3600-6 = 9 ⋅ 400 -6 = 9 ⋅ 400 - 9 + 3.

Somit gilt:

(907 + 3594) mod 9 ≡ (7 + 3) mod 9 ≡ 10 mod 9 ≡ 1 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(45 ⋅ 36) mod 11 ≡ (45 mod 11 ⋅ 36 mod 11) mod 11.

45 mod 11 ≡ 1 mod 11 kann man relativ leicht bestimmen, weil ja 45 = 44 + 1 = 4 ⋅ 11 + 1 ist.

36 mod 11 ≡ 3 mod 11 kann man relativ leicht bestimmen, weil ja 36 = 33 + 3 = 3 ⋅ 11 + 3 ist.

Somit gilt:

(45 ⋅ 36) mod 11 ≡ (1 ⋅ 3) mod 11 ≡ 3 mod 11.

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

2: 606²=606¹⁺¹=606¹⋅606¹ ≡ 606⋅606=367236 ≡ 178 mod 823

4: 606⁴=606²⁺²=606²⋅606² ≡ 178⋅178=31684 ≡ 410 mod 823

8: 606⁸=606⁴⁺⁴=606⁴⋅606⁴ ≡ 410⋅410=168100 ≡ 208 mod 823

16: 606¹⁶=606⁸⁺⁸=606⁸⋅606⁸ ≡ 208⋅208=43264 ≡ 468 mod 823

32: 606³²=606¹⁶⁺¹⁶=606¹⁶⋅606¹⁶ ≡ 468⋅468=219024 ≡ 106 mod 823

64: 606⁶⁴=606³²⁺³²=606³²⋅606³² ≡ 106⋅106=11236 ≡ 537 mod 823

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

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

91 = 64+16+8+2+1

299⁹¹

= 299^64+16+8+2+1

= 299⁶⁴⋅299¹⁶⋅299⁸⋅299²⋅299¹

≡ 768 ⋅ 596 ⋅ 458 ⋅ 197 ⋅ 299 mod 769
≡ 457728 ⋅ 458 ⋅ 197 ⋅ 299 mod 769 ≡ 173 ⋅ 458 ⋅ 197 ⋅ 299 mod 769
≡ 79234 ⋅ 197 ⋅ 299 mod 769 ≡ 27 ⋅ 197 ⋅ 299 mod 769
≡ 5319 ⋅ 299 mod 769 ≡ 705 ⋅ 299 mod 769
≡ 210795 mod 769 ≡ 89 mod 769

Es gilt also: 299⁹¹ ≡ 89 mod 769

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

=>79	= 1⋅42 + 37
=>42	= 1⋅37 + 5
=>37	= 7⋅5 + 2
=>5	= 2⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(79,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= 37-7⋅5	eingesetzt in die Zeile drüber:	1	= 1⋅5 -2⋅(37 -7⋅ 5) = 1⋅5 -2⋅37 +14⋅ 5) = -2⋅37 +15⋅ 5 (=1)
5= 42-1⋅37	eingesetzt in die Zeile drüber:	1	= -2⋅37 +15⋅(42 -1⋅ 37) = -2⋅37 +15⋅42 -15⋅ 37) = 15⋅42 -17⋅ 37 (=1)
37= 79-1⋅42	eingesetzt in die Zeile drüber:	1	= 15⋅42 -17⋅(79 -1⋅ 42) = 15⋅42 -17⋅79 +17⋅ 42) = -17⋅79 +32⋅ 42 (=1)

Es gilt also: ggt(79,42)=1 = -17⋅79 +32⋅42

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

1 +17⋅79 = +32⋅42

Es gilt also: 32⋅42 = 17⋅79 +1

Somit 32⋅42 = 1 mod 79

32 ist also das Inverse von 42 mod 79