Um längere Rechnungen zu vermeiden, rechnen wir:

(1796 - 11995) mod 6 ≡ (1796 mod 6 - 11995 mod 6) mod 6.

1796 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 1796 = 1800-4 = 6 ⋅ 300 -4 = 6 ⋅ 300 - 6 + 2.

11995 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 11995 = 12000-5 = 6 ⋅ 2000 -5 = 6 ⋅ 2000 - 6 + 1.

Somit gilt:

(1796 - 11995) mod 6 ≡ (2 - 1) mod 6 ≡ 1 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(100 ⋅ 99) mod 9 ≡ (100 mod 9 ⋅ 99 mod 9) mod 9.

100 mod 9 ≡ 1 mod 9 kann man relativ leicht bestimmen, weil ja 100 = 99 + 1 = 11 ⋅ 9 + 1 ist.

99 mod 9 ≡ 0 mod 9 kann man relativ leicht bestimmen, weil ja 99 = 99 + 0 = 11 ⋅ 9 + 0 ist.

Somit gilt:

(100 ⋅ 99) mod 9 ≡ (1 ⋅ 0) mod 9 ≡ 0 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: 422¹=422

2: 422²=422¹⁺¹=422¹⋅422¹ ≡ 422⋅422=178084 ≡ 698 mod 733

4: 422⁴=422²⁺²=422²⋅422² ≡ 698⋅698=487204 ≡ 492 mod 733

8: 422⁸=422⁴⁺⁴=422⁴⋅422⁴ ≡ 492⋅492=242064 ≡ 174 mod 733

16: 422¹⁶=422⁸⁺⁸=422⁸⋅422⁸ ≡ 174⋅174=30276 ≡ 223 mod 733

32: 422³²=422¹⁶⁺¹⁶=422¹⁶⋅422¹⁶ ≡ 223⋅223=49729 ≡ 618 mod 733

64: 422⁶⁴=422³²⁺³²=422³²⋅422³² ≡ 618⋅618=381924 ≡ 31 mod 733

128: 422¹²⁸=422⁶⁴⁺⁶⁴=422⁶⁴⋅422⁶⁴ ≡ 31⋅31=961 ≡ 228 mod 733

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

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

189 = 128+32+16+8+4+1

144¹⁸⁹

= 144^{128+32+16+8+4+1}

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

≡ 58 ⋅ 199 ⋅ 58 ⋅ 144 ⋅ 199 ⋅ 144 mod 211
≡ 11542 ⋅ 58 ⋅ 144 ⋅ 199 ⋅ 144 mod 211 ≡ 148 ⋅ 58 ⋅ 144 ⋅ 199 ⋅ 144 mod 211
≡ 8584 ⋅ 144 ⋅ 199 ⋅ 144 mod 211 ≡ 144 ⋅ 144 ⋅ 199 ⋅ 144 mod 211
≡ 20736 ⋅ 199 ⋅ 144 mod 211 ≡ 58 ⋅ 199 ⋅ 144 mod 211
≡ 11542 ⋅ 144 mod 211 ≡ 148 ⋅ 144 mod 211
≡ 21312 mod 211 ≡ 1 mod 211

Es gilt also: 144¹⁸⁹ ≡ 1 mod 211

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

=>83	= 1⋅43 + 40
=>43	= 1⋅40 + 3
=>40	= 13⋅3 + 1
=>3	= 3⋅1 + 0

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

Es gilt also: ggt(83,43)=1 = 14⋅83 -27⋅43

oder wenn man 14⋅83 auf die linke Seite bringt:

1 -14⋅83 = -27⋅43

-27⋅43 = -14⋅83 + 1 |+83⋅43

-27⋅43 + 83⋅43 = -14⋅83 + 83⋅43 + 1

(-27 + 83) ⋅ 43 = (-14 + 43) ⋅ 83 + 1

56⋅43 = 29⋅83 + 1

Es gilt also: 56⋅43 = 29⋅83 +1

Somit 56⋅43 = 1 mod 83

56 ist also das Inverse von 43 mod 83