Um längere Rechnungen zu vermeiden, rechnen wir:

(17991 - 3594) mod 9 ≡ (17991 mod 9 - 3594 mod 9) mod 9.

17991 mod 9 ≡ 0 mod 9 kann man relativ leicht bestimmen, weil ja 17991 = 18000-9 = 9 ⋅ 2000 -9 = 9 ⋅ 2000 - 9 + 0.

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:

(17991 - 3594) mod 9 ≡ (0 - 3) mod 9 ≡ -3 mod 9 ≡ 6 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(43 ⋅ 74) mod 5 ≡ (43 mod 5 ⋅ 74 mod 5) mod 5.

43 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 43 = 40 + 3 = 8 ⋅ 5 + 3 ist.

74 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 74 = 70 + 4 = 14 ⋅ 5 + 4 ist.

Somit gilt:

(43 ⋅ 74) mod 5 ≡ (3 ⋅ 4) mod 5 ≡ 12 mod 5 ≡ 2 mod 5.

Die 16 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: 261¹=261

2: 261²=261¹⁺¹=261¹⋅261¹ ≡ 261⋅261=68121 ≡ 345 mod 353

4: 261⁴=261²⁺²=261²⋅261² ≡ 345⋅345=119025 ≡ 64 mod 353

8: 261⁸=261⁴⁺⁴=261⁴⋅261⁴ ≡ 64⋅64=4096 ≡ 213 mod 353

16: 261¹⁶=261⁸⁺⁸=261⁸⋅261⁸ ≡ 213⋅213=45369 ≡ 185 mod 353

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

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

249 = 128+64+32+16+8+1

344²⁴⁹

= 344^{128+64+32+16+8+1}

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

≡ 111 ⋅ 383 ⋅ 308 ⋅ 251 ⋅ 447 ⋅ 344 mod 883
≡ 42513 ⋅ 308 ⋅ 251 ⋅ 447 ⋅ 344 mod 883 ≡ 129 ⋅ 308 ⋅ 251 ⋅ 447 ⋅ 344 mod 883
≡ 39732 ⋅ 251 ⋅ 447 ⋅ 344 mod 883 ≡ 880 ⋅ 251 ⋅ 447 ⋅ 344 mod 883
≡ 220880 ⋅ 447 ⋅ 344 mod 883 ≡ 130 ⋅ 447 ⋅ 344 mod 883
≡ 58110 ⋅ 344 mod 883 ≡ 715 ⋅ 344 mod 883
≡ 245960 mod 883 ≡ 486 mod 883

Es gilt also: 344²⁴⁹ ≡ 486 mod 883

Berechnung des größten gemeinsamen Teilers von 59 und 45

=>59	= 1⋅45 + 14
=>45	= 3⋅14 + 3
=>14	= 4⋅3 + 2
=>3	= 1⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(59,45)=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= 3-1⋅2
2= 14-4⋅3	eingesetzt in die Zeile drüber:	1	= 1⋅3 -1⋅(14 -4⋅ 3) = 1⋅3 -1⋅14 +4⋅ 3) = -1⋅14 +5⋅ 3 (=1)
3= 45-3⋅14	eingesetzt in die Zeile drüber:	1	= -1⋅14 +5⋅(45 -3⋅ 14) = -1⋅14 +5⋅45 -15⋅ 14) = 5⋅45 -16⋅ 14 (=1)
14= 59-1⋅45	eingesetzt in die Zeile drüber:	1	= 5⋅45 -16⋅(59 -1⋅ 45) = 5⋅45 -16⋅59 +16⋅ 45) = -16⋅59 +21⋅ 45 (=1)

Es gilt also: ggt(59,45)=1 = -16⋅59 +21⋅45

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

1 +16⋅59 = +21⋅45

Es gilt also: 21⋅45 = 16⋅59 +1

Somit 21⋅45 = 1 mod 59

21 ist also das Inverse von 45 mod 59