Um längere Rechnungen zu vermeiden, rechnen wir:

(242 - 3208) mod 8 ≡ (242 mod 8 - 3208 mod 8) mod 8.

242 mod 8 ≡ 2 mod 8 kann man relativ leicht bestimmen, weil ja 242 = 240+2 = 8 ⋅ 30 +2.

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

Somit gilt:

(242 - 3208) mod 8 ≡ (2 - 0) mod 8 ≡ 2 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(74 ⋅ 36) mod 11 ≡ (74 mod 11 ⋅ 36 mod 11) mod 11.

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

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

Somit gilt:

(74 ⋅ 36) mod 11 ≡ (8 ⋅ 3) mod 11 ≡ 24 mod 11 ≡ 2 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: 739¹=739

2: 739²=739¹⁺¹=739¹⋅739¹ ≡ 739⋅739=546121 ≡ 432 mod 911

4: 739⁴=739²⁺²=739²⋅739² ≡ 432⋅432=186624 ≡ 780 mod 911

8: 739⁸=739⁴⁺⁴=739⁴⋅739⁴ ≡ 780⋅780=608400 ≡ 763 mod 911

16: 739¹⁶=739⁸⁺⁸=739⁸⋅739⁸ ≡ 763⋅763=582169 ≡ 40 mod 911

32: 739³²=739¹⁶⁺¹⁶=739¹⁶⋅739¹⁶ ≡ 40⋅40=1600 ≡ 689 mod 911

64: 739⁶⁴=739³²⁺³²=739³²⋅739³² ≡ 689⋅689=474721 ≡ 90 mod 911

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

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

117 = 64+32+16+4+1

289¹¹⁷

= 289^64+32+16+4+1

= 289⁶⁴⋅289³²⋅289¹⁶⋅289⁴⋅289¹

≡ 504 ⋅ 592 ⋅ 522 ⋅ 50 ⋅ 289 mod 673
≡ 298368 ⋅ 522 ⋅ 50 ⋅ 289 mod 673 ≡ 229 ⋅ 522 ⋅ 50 ⋅ 289 mod 673
≡ 119538 ⋅ 50 ⋅ 289 mod 673 ≡ 417 ⋅ 50 ⋅ 289 mod 673
≡ 20850 ⋅ 289 mod 673 ≡ 660 ⋅ 289 mod 673
≡ 190740 mod 673 ≡ 281 mod 673

Es gilt also: 289¹¹⁷ ≡ 281 mod 673

Berechnung des größten gemeinsamen Teilers von 73 und 56

=>73	= 1⋅56 + 17
=>56	= 3⋅17 + 5
=>17	= 3⋅5 + 2
=>5	= 2⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(73,56)=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= 5-2⋅2
2= 17-3⋅5	eingesetzt in die Zeile drüber:	1	= 1⋅5 -2⋅(17 -3⋅ 5) = 1⋅5 -2⋅17 +6⋅ 5) = -2⋅17 +7⋅ 5 (=1)
5= 56-3⋅17	eingesetzt in die Zeile drüber:	1	= -2⋅17 +7⋅(56 -3⋅ 17) = -2⋅17 +7⋅56 -21⋅ 17) = 7⋅56 -23⋅ 17 (=1)
17= 73-1⋅56	eingesetzt in die Zeile drüber:	1	= 7⋅56 -23⋅(73 -1⋅ 56) = 7⋅56 -23⋅73 +23⋅ 56) = -23⋅73 +30⋅ 56 (=1)

Es gilt also: ggt(73,56)=1 = -23⋅73 +30⋅56

oder wenn man -23⋅73 auf die linke Seite bringt:

1 +23⋅73 = +30⋅56

Es gilt also: 30⋅56 = 23⋅73 +1

Somit 30⋅56 = 1 mod 73

30 ist also das Inverse von 56 mod 73