Um längere Rechnungen zu vermeiden, rechnen wir:

(2695 + 44999) mod 9 ≡ (2695 mod 9 + 44999 mod 9) mod 9.

2695 mod 9 ≡ 4 mod 9 kann man relativ leicht bestimmen, weil ja 2695 = 2700-5 = 9 ⋅ 300 -5 = 9 ⋅ 300 - 9 + 4.

44999 mod 9 ≡ 8 mod 9 kann man relativ leicht bestimmen, weil ja 44999 = 45000-1 = 9 ⋅ 5000 -1 = 9 ⋅ 5000 - 9 + 8.

Somit gilt:

(2695 + 44999) mod 9 ≡ (4 + 8) mod 9 ≡ 12 mod 9 ≡ 3 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(47 ⋅ 97) mod 10 ≡ (47 mod 10 ⋅ 97 mod 10) mod 10.

47 mod 10 ≡ 7 mod 10 kann man relativ leicht bestimmen, weil ja 47 = 40 + 7 = 4 ⋅ 10 + 7 ist.

97 mod 10 ≡ 7 mod 10 kann man relativ leicht bestimmen, weil ja 97 = 90 + 7 = 9 ⋅ 10 + 7 ist.

Somit gilt:

(47 ⋅ 97) mod 10 ≡ (7 ⋅ 7) mod 10 ≡ 49 mod 10 ≡ 9 mod 10.

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

2: 191²=191¹⁺¹=191¹⋅191¹ ≡ 191⋅191=36481 ≡ 391 mod 401

4: 191⁴=191²⁺²=191²⋅191² ≡ 391⋅391=152881 ≡ 100 mod 401

8: 191⁸=191⁴⁺⁴=191⁴⋅191⁴ ≡ 100⋅100=10000 ≡ 376 mod 401

16: 191¹⁶=191⁸⁺⁸=191⁸⋅191⁸ ≡ 376⋅376=141376 ≡ 224 mod 401

32: 191³²=191¹⁶⁺¹⁶=191¹⁶⋅191¹⁶ ≡ 224⋅224=50176 ≡ 51 mod 401

64: 191⁶⁴=191³²⁺³²=191³²⋅191³² ≡ 51⋅51=2601 ≡ 195 mod 401

128: 191¹²⁸=191⁶⁴⁺⁶⁴=191⁶⁴⋅191⁶⁴ ≡ 195⋅195=38025 ≡ 331 mod 401

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

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

85 = 64+16+4+1

523⁸⁵

= 523^64+16+4+1

= 523⁶⁴⋅523¹⁶⋅523⁴⋅523¹

≡ 498 ⋅ 343 ⋅ 255 ⋅ 523 mod 877
≡ 170814 ⋅ 255 ⋅ 523 mod 877 ≡ 676 ⋅ 255 ⋅ 523 mod 877
≡ 172380 ⋅ 523 mod 877 ≡ 488 ⋅ 523 mod 877
≡ 255224 mod 877 ≡ 17 mod 877

Es gilt also: 523⁸⁵ ≡ 17 mod 877

Berechnung des größten gemeinsamen Teilers von 97 und 83

=>97	= 1⋅83 + 14
=>83	= 5⋅14 + 13
=>14	= 1⋅13 + 1
=>13	= 13⋅1 + 0

also gilt: ggt(97,83)=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= 14-1⋅13
13= 83-5⋅14	eingesetzt in die Zeile drüber:	1	= 1⋅14 -1⋅(83 -5⋅ 14) = 1⋅14 -1⋅83 +5⋅ 14) = -1⋅83 +6⋅ 14 (=1)
14= 97-1⋅83	eingesetzt in die Zeile drüber:	1	= -1⋅83 +6⋅(97 -1⋅ 83) = -1⋅83 +6⋅97 -6⋅ 83) = 6⋅97 -7⋅ 83 (=1)

Es gilt also: ggt(97,83)=1 = 6⋅97 -7⋅83

oder wenn man 6⋅97 auf die linke Seite bringt:

1 -6⋅97 = -7⋅83

-7⋅83 = -6⋅97 + 1 |+97⋅83

-7⋅83 + 97⋅83 = -6⋅97 + 97⋅83 + 1

(-7 + 97) ⋅ 83 = (-6 + 83) ⋅ 97 + 1

90⋅83 = 77⋅97 + 1

Es gilt also: 90⋅83 = 77⋅97 +1

Somit 90⋅83 = 1 mod 97

90 ist also das Inverse von 83 mod 97