Um längere Rechnungen zu vermeiden, rechnen wir:

(797 + 121) mod 4 ≡ (797 mod 4 + 121 mod 4) mod 4.

797 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 797 = 700+97 = 4 ⋅ 175 +97.

121 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 121 = 120+1 = 4 ⋅ 30 +1.

Somit gilt:

(797 + 121) mod 4 ≡ (1 + 1) mod 4 ≡ 2 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(35 ⋅ 87) mod 9 ≡ (35 mod 9 ⋅ 87 mod 9) mod 9.

35 mod 9 ≡ 8 mod 9 kann man relativ leicht bestimmen, weil ja 35 = 27 + 8 = 3 ⋅ 9 + 8 ist.

87 mod 9 ≡ 6 mod 9 kann man relativ leicht bestimmen, weil ja 87 = 81 + 6 = 9 ⋅ 9 + 6 ist.

Somit gilt:

(35 ⋅ 87) mod 9 ≡ (8 ⋅ 6) mod 9 ≡ 48 mod 9 ≡ 3 mod 9.

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

2: 728²=728¹⁺¹=728¹⋅728¹ ≡ 728⋅728=529984 ≡ 503 mod 881

4: 728⁴=728²⁺²=728²⋅728² ≡ 503⋅503=253009 ≡ 162 mod 881

8: 728⁸=728⁴⁺⁴=728⁴⋅728⁴ ≡ 162⋅162=26244 ≡ 695 mod 881

16: 728¹⁶=728⁸⁺⁸=728⁸⋅728⁸ ≡ 695⋅695=483025 ≡ 237 mod 881

32: 728³²=728¹⁶⁺¹⁶=728¹⁶⋅728¹⁶ ≡ 237⋅237=56169 ≡ 666 mod 881

64: 728⁶⁴=728³²⁺³²=728³²⋅728³² ≡ 666⋅666=443556 ≡ 413 mod 881

128: 728¹²⁸=728⁶⁴⁺⁶⁴=728⁶⁴⋅728⁶⁴ ≡ 413⋅413=170569 ≡ 536 mod 881

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

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

62 = 32+16+8+4+2

329⁶²

= 329^32+16+8+4+2

= 329³²⋅329¹⁶⋅329⁸⋅329⁴⋅329²

≡ 4 ⋅ 329 ⋅ 256 ⋅ 16 ⋅ 4 mod 331
≡ 1316 ⋅ 256 ⋅ 16 ⋅ 4 mod 331 ≡ 323 ⋅ 256 ⋅ 16 ⋅ 4 mod 331
≡ 82688 ⋅ 16 ⋅ 4 mod 331 ≡ 269 ⋅ 16 ⋅ 4 mod 331
≡ 4304 ⋅ 4 mod 331 ≡ 1 ⋅ 4 mod 331
≡ 4 mod 331

Es gilt also: 329⁶² ≡ 4 mod 331

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

=>61	= 1⋅42 + 19
=>42	= 2⋅19 + 4
=>19	= 4⋅4 + 3
=>4	= 1⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(61,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= 4-1⋅3
3= 19-4⋅4	eingesetzt in die Zeile drüber:	1	= 1⋅4 -1⋅(19 -4⋅ 4) = 1⋅4 -1⋅19 +4⋅ 4) = -1⋅19 +5⋅ 4 (=1)
4= 42-2⋅19	eingesetzt in die Zeile drüber:	1	= -1⋅19 +5⋅(42 -2⋅ 19) = -1⋅19 +5⋅42 -10⋅ 19) = 5⋅42 -11⋅ 19 (=1)
19= 61-1⋅42	eingesetzt in die Zeile drüber:	1	= 5⋅42 -11⋅(61 -1⋅ 42) = 5⋅42 -11⋅61 +11⋅ 42) = -11⋅61 +16⋅ 42 (=1)

Es gilt also: ggt(61,42)=1 = -11⋅61 +16⋅42

oder wenn man -11⋅61 auf die linke Seite bringt:

1 +11⋅61 = +16⋅42

Es gilt also: 16⋅42 = 11⋅61 +1

Somit 16⋅42 = 1 mod 61

16 ist also das Inverse von 42 mod 61