Um längere Rechnungen zu vermeiden, rechnen wir:

(1602 + 7995) mod 8 ≡ (1602 mod 8 + 7995 mod 8) mod 8.

1602 mod 8 ≡ 2 mod 8 kann man relativ leicht bestimmen, weil ja 1602 = 1600+2 = 8 ⋅ 200 +2.

7995 mod 8 ≡ 3 mod 8 kann man relativ leicht bestimmen, weil ja 7995 = 7000+995 = 8 ⋅ 875 +995.

Somit gilt:

(1602 + 7995) mod 8 ≡ (2 + 3) mod 8 ≡ 5 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(71 ⋅ 34) mod 8 ≡ (71 mod 8 ⋅ 34 mod 8) mod 8.

71 mod 8 ≡ 7 mod 8 kann man relativ leicht bestimmen, weil ja 71 = 64 + 7 = 8 ⋅ 8 + 7 ist.

34 mod 8 ≡ 2 mod 8 kann man relativ leicht bestimmen, weil ja 34 = 32 + 2 = 4 ⋅ 8 + 2 ist.

Somit gilt:

(71 ⋅ 34) mod 8 ≡ (7 ⋅ 2) mod 8 ≡ 14 mod 8 ≡ 6 mod 8.

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

2: 99²=99¹⁺¹=99¹⋅99¹ ≡ 99⋅99=9801 ≡ 45 mod 271

4: 99⁴=99²⁺²=99²⋅99² ≡ 45⋅45=2025 ≡ 128 mod 271

8: 99⁸=99⁴⁺⁴=99⁴⋅99⁴ ≡ 128⋅128=16384 ≡ 124 mod 271

16: 99¹⁶=99⁸⁺⁸=99⁸⋅99⁸ ≡ 124⋅124=15376 ≡ 200 mod 271

32: 99³²=99¹⁶⁺¹⁶=99¹⁶⋅99¹⁶ ≡ 200⋅200=40000 ≡ 163 mod 271

64: 99⁶⁴=99³²⁺³²=99³²⋅99³² ≡ 163⋅163=26569 ≡ 11 mod 271

128: 99¹²⁸=99⁶⁴⁺⁶⁴=99⁶⁴⋅99⁶⁴ ≡ 11⋅11=121 ≡ 121 mod 271

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

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

95 = 64+16+8+4+2+1

154⁹⁵

= 154^{64+16+8+4+2+1}

= 154⁶⁴⋅154¹⁶⋅154⁸⋅154⁴⋅154²⋅154¹

≡ 113 ⋅ 237 ⋅ 246 ⋅ 23 ⋅ 227 ⋅ 154 mod 283
≡ 26781 ⋅ 246 ⋅ 23 ⋅ 227 ⋅ 154 mod 283 ≡ 179 ⋅ 246 ⋅ 23 ⋅ 227 ⋅ 154 mod 283
≡ 44034 ⋅ 23 ⋅ 227 ⋅ 154 mod 283 ≡ 169 ⋅ 23 ⋅ 227 ⋅ 154 mod 283
≡ 3887 ⋅ 227 ⋅ 154 mod 283 ≡ 208 ⋅ 227 ⋅ 154 mod 283
≡ 47216 ⋅ 154 mod 283 ≡ 238 ⋅ 154 mod 283
≡ 36652 mod 283 ≡ 145 mod 283

Es gilt also: 154⁹⁵ ≡ 145 mod 283

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

=>79	= 1⋅63 + 16
=>63	= 3⋅16 + 15
=>16	= 1⋅15 + 1
=>15	= 15⋅1 + 0

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

Es gilt also: ggt(79,63)=1 = 4⋅79 -5⋅63

oder wenn man 4⋅79 auf die linke Seite bringt:

1 -4⋅79 = -5⋅63

-5⋅63 = -4⋅79 + 1 |+79⋅63

-5⋅63 + 79⋅63 = -4⋅79 + 79⋅63 + 1

(-5 + 79) ⋅ 63 = (-4 + 63) ⋅ 79 + 1

74⋅63 = 59⋅79 + 1

Es gilt also: 74⋅63 = 59⋅79 +1

Somit 74⋅63 = 1 mod 79

74 ist also das Inverse von 63 mod 79