Um längere Rechnungen zu vermeiden, rechnen wir:

(211 - 7006) mod 7 ≡ (211 mod 7 - 7006 mod 7) mod 7.

211 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 211 = 210+1 = 7 ⋅ 30 +1.

7006 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 7006 = 7000+6 = 7 ⋅ 1000 +6.

Somit gilt:

(211 - 7006) mod 7 ≡ (1 - 6) mod 7 ≡ -5 mod 7 ≡ 2 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(45 ⋅ 66) mod 5 ≡ (45 mod 5 ⋅ 66 mod 5) mod 5.

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

66 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 66 = 65 + 1 = 13 ⋅ 5 + 1 ist.

Somit gilt:

(45 ⋅ 66) mod 5 ≡ (0 ⋅ 1) mod 5 ≡ 0 mod 5.

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

2: 221²=221¹⁺¹=221¹⋅221¹ ≡ 221⋅221=48841 ≡ 330 mod 349

4: 221⁴=221²⁺²=221²⋅221² ≡ 330⋅330=108900 ≡ 12 mod 349

8: 221⁸=221⁴⁺⁴=221⁴⋅221⁴ ≡ 12⋅12=144 ≡ 144 mod 349

16: 221¹⁶=221⁸⁺⁸=221⁸⋅221⁸ ≡ 144⋅144=20736 ≡ 145 mod 349

32: 221³²=221¹⁶⁺¹⁶=221¹⁶⋅221¹⁶ ≡ 145⋅145=21025 ≡ 85 mod 349

64: 221⁶⁴=221³²⁺³²=221³²⋅221³² ≡ 85⋅85=7225 ≡ 245 mod 349

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

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

249 = 128+64+32+16+8+1

177²⁴⁹

= 177^{128+64+32+16+8+1}

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

≡ 254 ⋅ 172 ⋅ 256 ⋅ 16 ⋅ 4 ⋅ 177 mod 419
≡ 43688 ⋅ 256 ⋅ 16 ⋅ 4 ⋅ 177 mod 419 ≡ 112 ⋅ 256 ⋅ 16 ⋅ 4 ⋅ 177 mod 419
≡ 28672 ⋅ 16 ⋅ 4 ⋅ 177 mod 419 ≡ 180 ⋅ 16 ⋅ 4 ⋅ 177 mod 419
≡ 2880 ⋅ 4 ⋅ 177 mod 419 ≡ 366 ⋅ 4 ⋅ 177 mod 419
≡ 1464 ⋅ 177 mod 419 ≡ 207 ⋅ 177 mod 419
≡ 36639 mod 419 ≡ 186 mod 419

Es gilt also: 177²⁴⁹ ≡ 186 mod 419

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

=>67	= 1⋅52 + 15
=>52	= 3⋅15 + 7
=>15	= 2⋅7 + 1
=>7	= 7⋅1 + 0

also gilt: ggt(67,52)=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= 15-2⋅7
7= 52-3⋅15	eingesetzt in die Zeile drüber:	1	= 1⋅15 -2⋅(52 -3⋅ 15) = 1⋅15 -2⋅52 +6⋅ 15) = -2⋅52 +7⋅ 15 (=1)
15= 67-1⋅52	eingesetzt in die Zeile drüber:	1	= -2⋅52 +7⋅(67 -1⋅ 52) = -2⋅52 +7⋅67 -7⋅ 52) = 7⋅67 -9⋅ 52 (=1)

Es gilt also: ggt(67,52)=1 = 7⋅67 -9⋅52

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

1 -7⋅67 = -9⋅52

-9⋅52 = -7⋅67 + 1 |+67⋅52

-9⋅52 + 67⋅52 = -7⋅67 + 67⋅52 + 1

(-9 + 67) ⋅ 52 = (-7 + 52) ⋅ 67 + 1

58⋅52 = 45⋅67 + 1

Es gilt also: 58⋅52 = 45⋅67 +1

Somit 58⋅52 = 1 mod 67

58 ist also das Inverse von 52 mod 67