Um längere Rechnungen zu vermeiden, rechnen wir:

(262 - 273) mod 9 ≡ (262 mod 9 - 273 mod 9) mod 9.

262 mod 9 ≡ 1 mod 9 kann man relativ leicht bestimmen, weil ja 262 = 270-8 = 9 ⋅ 30 -8 = 9 ⋅ 30 - 9 + 1.

273 mod 9 ≡ 3 mod 9 kann man relativ leicht bestimmen, weil ja 273 = 270+3 = 9 ⋅ 30 +3.

Somit gilt:

(262 - 273) mod 9 ≡ (1 - 3) mod 9 ≡ -2 mod 9 ≡ 7 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(63 ⋅ 76) mod 4 ≡ (63 mod 4 ⋅ 76 mod 4) mod 4.

63 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 63 = 60 + 3 = 15 ⋅ 4 + 3 ist.

76 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 76 = 76 + 0 = 19 ⋅ 4 + 0 ist.

Somit gilt:

(63 ⋅ 76) mod 4 ≡ (3 ⋅ 0) mod 4 ≡ 0 mod 4.

Die 64 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: 364¹=364

2: 364²=364¹⁺¹=364¹⋅364¹ ≡ 364⋅364=132496 ≡ 295 mod 397

4: 364⁴=364²⁺²=364²⋅364² ≡ 295⋅295=87025 ≡ 82 mod 397

8: 364⁸=364⁴⁺⁴=364⁴⋅364⁴ ≡ 82⋅82=6724 ≡ 372 mod 397

16: 364¹⁶=364⁸⁺⁸=364⁸⋅364⁸ ≡ 372⋅372=138384 ≡ 228 mod 397

32: 364³²=364¹⁶⁺¹⁶=364¹⁶⋅364¹⁶ ≡ 228⋅228=51984 ≡ 374 mod 397

64: 364⁶⁴=364³²⁺³²=364³²⋅364³² ≡ 374⋅374=139876 ≡ 132 mod 397

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

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

179 = 128+32+16+2+1

400¹⁷⁹

= 400^{128+32+16+2+1}

= 400¹²⁸⋅400³²⋅400¹⁶⋅400²⋅400¹

≡ 420 ⋅ 555 ⋅ 420 ⋅ 197 ⋅ 400 mod 617
≡ 233100 ⋅ 420 ⋅ 197 ⋅ 400 mod 617 ≡ 491 ⋅ 420 ⋅ 197 ⋅ 400 mod 617
≡ 206220 ⋅ 197 ⋅ 400 mod 617 ≡ 142 ⋅ 197 ⋅ 400 mod 617
≡ 27974 ⋅ 400 mod 617 ≡ 209 ⋅ 400 mod 617
≡ 83600 mod 617 ≡ 305 mod 617

Es gilt also: 400¹⁷⁹ ≡ 305 mod 617

Berechnung des größten gemeinsamen Teilers von 67 und 36

=>67	= 1⋅36 + 31
=>36	= 1⋅31 + 5
=>31	= 6⋅5 + 1
=>5	= 5⋅1 + 0

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

Es gilt also: ggt(67,36)=1 = 7⋅67 -13⋅36

oder wenn man 7⋅67 auf die linke Seite bringt:

1 -7⋅67 = -13⋅36

-13⋅36 = -7⋅67 + 1 |+67⋅36

-13⋅36 + 67⋅36 = -7⋅67 + 67⋅36 + 1

(-13 + 67) ⋅ 36 = (-7 + 36) ⋅ 67 + 1

54⋅36 = 29⋅67 + 1

Es gilt also: 54⋅36 = 29⋅67 +1

Somit 54⋅36 = 1 mod 67

54 ist also das Inverse von 36 mod 67