Um längere Rechnungen zu vermeiden, rechnen wir:

(4496 - 4501) mod 9 ≡ (4496 mod 9 - 4501 mod 9) mod 9.

4496 mod 9 ≡ 5 mod 9 kann man relativ leicht bestimmen, weil ja 4496 = 4500-4 = 9 ⋅ 500 -4 = 9 ⋅ 500 - 9 + 5.

4501 mod 9 ≡ 1 mod 9 kann man relativ leicht bestimmen, weil ja 4501 = 4500+1 = 9 ⋅ 500 +1.

Somit gilt:

(4496 - 4501) mod 9 ≡ (5 - 1) mod 9 ≡ 4 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(37 ⋅ 25) mod 7 ≡ (37 mod 7 ⋅ 25 mod 7) mod 7.

37 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 37 = 35 + 2 = 5 ⋅ 7 + 2 ist.

25 mod 7 ≡ 4 mod 7 kann man relativ leicht bestimmen, weil ja 25 = 21 + 4 = 3 ⋅ 7 + 4 ist.

Somit gilt:

(37 ⋅ 25) mod 7 ≡ (2 ⋅ 4) mod 7 ≡ 8 mod 7 ≡ 1 mod 7.

Die 32 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: 406¹=406

2: 406²=406¹⁺¹=406¹⋅406¹ ≡ 406⋅406=164836 ≡ 280 mod 653

4: 406⁴=406²⁺²=406²⋅406² ≡ 280⋅280=78400 ≡ 40 mod 653

8: 406⁸=406⁴⁺⁴=406⁴⋅406⁴ ≡ 40⋅40=1600 ≡ 294 mod 653

16: 406¹⁶=406⁸⁺⁸=406⁸⋅406⁸ ≡ 294⋅294=86436 ≡ 240 mod 653

32: 406³²=406¹⁶⁺¹⁶=406¹⁶⋅406¹⁶ ≡ 240⋅240=57600 ≡ 136 mod 653

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

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

218 = 128+64+16+8+2

148²¹⁸

= 148^{128+64+16+8+2}

= 148¹²⁸⋅148⁶⁴⋅148¹⁶⋅148⁸⋅148²

≡ 158 ⋅ 182 ⋅ 240 ⋅ 193 ⋅ 134 mod 311
≡ 28756 ⋅ 240 ⋅ 193 ⋅ 134 mod 311 ≡ 144 ⋅ 240 ⋅ 193 ⋅ 134 mod 311
≡ 34560 ⋅ 193 ⋅ 134 mod 311 ≡ 39 ⋅ 193 ⋅ 134 mod 311
≡ 7527 ⋅ 134 mod 311 ≡ 63 ⋅ 134 mod 311
≡ 8442 mod 311 ≡ 45 mod 311

Es gilt also: 148²¹⁸ ≡ 45 mod 311

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

=>67	= 2⋅28 + 11
=>28	= 2⋅11 + 6
=>11	= 1⋅6 + 5
=>6	= 1⋅5 + 1
=>5	= 5⋅1 + 0

also gilt: ggt(67,28)=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= 6-1⋅5
5= 11-1⋅6	eingesetzt in die Zeile drüber:	1	= 1⋅6 -1⋅(11 -1⋅ 6) = 1⋅6 -1⋅11 +1⋅ 6) = -1⋅11 +2⋅ 6 (=1)
6= 28-2⋅11	eingesetzt in die Zeile drüber:	1	= -1⋅11 +2⋅(28 -2⋅ 11) = -1⋅11 +2⋅28 -4⋅ 11) = 2⋅28 -5⋅ 11 (=1)
11= 67-2⋅28	eingesetzt in die Zeile drüber:	1	= 2⋅28 -5⋅(67 -2⋅ 28) = 2⋅28 -5⋅67 +10⋅ 28) = -5⋅67 +12⋅ 28 (=1)

Es gilt also: ggt(67,28)=1 = -5⋅67 +12⋅28

oder wenn man -5⋅67 auf die linke Seite bringt:

1 +5⋅67 = +12⋅28

Es gilt also: 12⋅28 = 5⋅67 +1

Somit 12⋅28 = 1 mod 67

12 ist also das Inverse von 28 mod 67