Um längere Rechnungen zu vermeiden, rechnen wir:

(210 - 66) mod 7 ≡ (210 mod 7 - 66 mod 7) mod 7.

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

66 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 66 = 70-4 = 7 ⋅ 10 -4 = 7 ⋅ 10 - 7 + 3.

Somit gilt:

(210 - 66) mod 7 ≡ (0 - 3) mod 7 ≡ -3 mod 7 ≡ 4 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(34 ⋅ 58) mod 3 ≡ (34 mod 3 ⋅ 58 mod 3) mod 3.

34 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 34 = 33 + 1 = 11 ⋅ 3 + 1 ist.

58 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 58 = 57 + 1 = 19 ⋅ 3 + 1 ist.

Somit gilt:

(34 ⋅ 58) mod 3 ≡ (1 ⋅ 1) mod 3 ≡ 1 mod 3.

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

2: 217²=217¹⁺¹=217¹⋅217¹ ≡ 217⋅217=47089 ≡ 267 mod 571

4: 217⁴=217²⁺²=217²⋅217² ≡ 267⋅267=71289 ≡ 485 mod 571

8: 217⁸=217⁴⁺⁴=217⁴⋅217⁴ ≡ 485⋅485=235225 ≡ 544 mod 571

16: 217¹⁶=217⁸⁺⁸=217⁸⋅217⁸ ≡ 544⋅544=295936 ≡ 158 mod 571

32: 217³²=217¹⁶⁺¹⁶=217¹⁶⋅217¹⁶ ≡ 158⋅158=24964 ≡ 411 mod 571

64: 217⁶⁴=217³²⁺³²=217³²⋅217³² ≡ 411⋅411=168921 ≡ 476 mod 571

128: 217¹²⁸=217⁶⁴⁺⁶⁴=217⁶⁴⋅217⁶⁴ ≡ 476⋅476=226576 ≡ 460 mod 571

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

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

91 = 64+16+8+2+1

290⁹¹

= 290^64+16+8+2+1

= 290⁶⁴⋅290¹⁶⋅290⁸⋅290²⋅290¹

≡ 59 ⋅ 40 ⋅ 115 ⋅ 9 ⋅ 290 mod 293
≡ 2360 ⋅ 115 ⋅ 9 ⋅ 290 mod 293 ≡ 16 ⋅ 115 ⋅ 9 ⋅ 290 mod 293
≡ 1840 ⋅ 9 ⋅ 290 mod 293 ≡ 82 ⋅ 9 ⋅ 290 mod 293
≡ 738 ⋅ 290 mod 293 ≡ 152 ⋅ 290 mod 293
≡ 44080 mod 293 ≡ 130 mod 293

Es gilt also: 290⁹¹ ≡ 130 mod 293

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

=>67	= 1⋅44 + 23
=>44	= 1⋅23 + 21
=>23	= 1⋅21 + 2
=>21	= 10⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(67,44)=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= 21-10⋅2
2= 23-1⋅21	eingesetzt in die Zeile drüber:	1	= 1⋅21 -10⋅(23 -1⋅ 21) = 1⋅21 -10⋅23 +10⋅ 21) = -10⋅23 +11⋅ 21 (=1)
21= 44-1⋅23	eingesetzt in die Zeile drüber:	1	= -10⋅23 +11⋅(44 -1⋅ 23) = -10⋅23 +11⋅44 -11⋅ 23) = 11⋅44 -21⋅ 23 (=1)
23= 67-1⋅44	eingesetzt in die Zeile drüber:	1	= 11⋅44 -21⋅(67 -1⋅ 44) = 11⋅44 -21⋅67 +21⋅ 44) = -21⋅67 +32⋅ 44 (=1)

Es gilt also: ggt(67,44)=1 = -21⋅67 +32⋅44

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

1 +21⋅67 = +32⋅44

Es gilt also: 32⋅44 = 21⋅67 +1

Somit 32⋅44 = 1 mod 67

32 ist also das Inverse von 44 mod 67