Um längere Rechnungen zu vermeiden, rechnen wir:

(3207 - 24006) mod 8 ≡ (3207 mod 8 - 24006 mod 8) mod 8.

3207 mod 8 ≡ 7 mod 8 kann man relativ leicht bestimmen, weil ja 3207 = 3200+7 = 8 ⋅ 400 +7.

24006 mod 8 ≡ 6 mod 8 kann man relativ leicht bestimmen, weil ja 24006 = 24000+6 = 8 ⋅ 3000 +6.

Somit gilt:

(3207 - 24006) mod 8 ≡ (7 - 6) mod 8 ≡ 1 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(72 ⋅ 62) mod 11 ≡ (72 mod 11 ⋅ 62 mod 11) mod 11.

72 mod 11 ≡ 6 mod 11 kann man relativ leicht bestimmen, weil ja 72 = 66 + 6 = 6 ⋅ 11 + 6 ist.

62 mod 11 ≡ 7 mod 11 kann man relativ leicht bestimmen, weil ja 62 = 55 + 7 = 5 ⋅ 11 + 7 ist.

Somit gilt:

(72 ⋅ 62) mod 11 ≡ (6 ⋅ 7) mod 11 ≡ 42 mod 11 ≡ 9 mod 11.

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

2: 353²=353¹⁺¹=353¹⋅353¹ ≡ 353⋅353=124609 ≡ 713 mod 911

4: 353⁴=353²⁺²=353²⋅353² ≡ 713⋅713=508369 ≡ 31 mod 911

8: 353⁸=353⁴⁺⁴=353⁴⋅353⁴ ≡ 31⋅31=961 ≡ 50 mod 911

16: 353¹⁶=353⁸⁺⁸=353⁸⋅353⁸ ≡ 50⋅50=2500 ≡ 678 mod 911

32: 353³²=353¹⁶⁺¹⁶=353¹⁶⋅353¹⁶ ≡ 678⋅678=459684 ≡ 540 mod 911

64: 353⁶⁴=353³²⁺³²=353³²⋅353³² ≡ 540⋅540=291600 ≡ 80 mod 911

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

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

94 = 64+16+8+4+2

820⁹⁴

= 820^64+16+8+4+2

= 820⁶⁴⋅820¹⁶⋅820⁸⋅820⁴⋅820²

≡ 640 ⋅ 564 ⋅ 666 ⋅ 276 ⋅ 361 mod 839
≡ 360960 ⋅ 666 ⋅ 276 ⋅ 361 mod 839 ≡ 190 ⋅ 666 ⋅ 276 ⋅ 361 mod 839
≡ 126540 ⋅ 276 ⋅ 361 mod 839 ≡ 690 ⋅ 276 ⋅ 361 mod 839
≡ 190440 ⋅ 361 mod 839 ≡ 826 ⋅ 361 mod 839
≡ 298186 mod 839 ≡ 341 mod 839

Es gilt also: 820⁹⁴ ≡ 341 mod 839

Berechnung des größten gemeinsamen Teilers von 71 und 55

=>71	= 1⋅55 + 16
=>55	= 3⋅16 + 7
=>16	= 2⋅7 + 2
=>7	= 3⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(71,55)=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= 7-3⋅2
2= 16-2⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -3⋅(16 -2⋅ 7) = 1⋅7 -3⋅16 +6⋅ 7) = -3⋅16 +7⋅ 7 (=1)
7= 55-3⋅16	eingesetzt in die Zeile drüber:	1	= -3⋅16 +7⋅(55 -3⋅ 16) = -3⋅16 +7⋅55 -21⋅ 16) = 7⋅55 -24⋅ 16 (=1)
16= 71-1⋅55	eingesetzt in die Zeile drüber:	1	= 7⋅55 -24⋅(71 -1⋅ 55) = 7⋅55 -24⋅71 +24⋅ 55) = -24⋅71 +31⋅ 55 (=1)

Es gilt also: ggt(71,55)=1 = -24⋅71 +31⋅55

oder wenn man -24⋅71 auf die linke Seite bringt:

1 +24⋅71 = +31⋅55

Es gilt also: 31⋅55 = 24⋅71 +1

Somit 31⋅55 = 1 mod 71

31 ist also das Inverse von 55 mod 71