Um längere Rechnungen zu vermeiden, rechnen wir:

(282 + 209) mod 7 ≡ (282 mod 7 + 209 mod 7) mod 7.

282 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 282 = 280+2 = 7 ⋅ 40 +2.

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

Somit gilt:

(282 + 209) mod 7 ≡ (2 + 6) mod 7 ≡ 8 mod 7 ≡ 1 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(15 ⋅ 74) mod 4 ≡ (15 mod 4 ⋅ 74 mod 4) mod 4.

15 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 15 = 12 + 3 = 3 ⋅ 4 + 3 ist.

74 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 74 = 72 + 2 = 18 ⋅ 4 + 2 ist.

Somit gilt:

(15 ⋅ 74) mod 4 ≡ (3 ⋅ 2) mod 4 ≡ 6 mod 4 ≡ 2 mod 4.

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

2: 148²=148¹⁺¹=148¹⋅148¹ ≡ 148⋅148=21904 ≡ 214 mod 241

4: 148⁴=148²⁺²=148²⋅148² ≡ 214⋅214=45796 ≡ 6 mod 241

8: 148⁸=148⁴⁺⁴=148⁴⋅148⁴ ≡ 6⋅6=36 ≡ 36 mod 241

16: 148¹⁶=148⁸⁺⁸=148⁸⋅148⁸ ≡ 36⋅36=1296 ≡ 91 mod 241

32: 148³²=148¹⁶⁺¹⁶=148¹⁶⋅148¹⁶ ≡ 91⋅91=8281 ≡ 87 mod 241

64: 148⁶⁴=148³²⁺³²=148³²⋅148³² ≡ 87⋅87=7569 ≡ 98 mod 241

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

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

252 = 128+64+32+16+8+4

673²⁵²

= 673^{128+64+32+16+8+4}

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

≡ 344 ⋅ 516 ⋅ 348 ⋅ 179 ⋅ 540 ⋅ 82 mod 773
≡ 177504 ⋅ 348 ⋅ 179 ⋅ 540 ⋅ 82 mod 773 ≡ 487 ⋅ 348 ⋅ 179 ⋅ 540 ⋅ 82 mod 773
≡ 169476 ⋅ 179 ⋅ 540 ⋅ 82 mod 773 ≡ 189 ⋅ 179 ⋅ 540 ⋅ 82 mod 773
≡ 33831 ⋅ 540 ⋅ 82 mod 773 ≡ 592 ⋅ 540 ⋅ 82 mod 773
≡ 319680 ⋅ 82 mod 773 ≡ 431 ⋅ 82 mod 773
≡ 35342 mod 773 ≡ 557 mod 773

Es gilt also: 673²⁵² ≡ 557 mod 773

Berechnung des größten gemeinsamen Teilers von 79 und 69

=>79	= 1⋅69 + 10
=>69	= 6⋅10 + 9
=>10	= 1⋅9 + 1
=>9	= 9⋅1 + 0

also gilt: ggt(79,69)=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= 10-1⋅9
9= 69-6⋅10	eingesetzt in die Zeile drüber:	1	= 1⋅10 -1⋅(69 -6⋅ 10) = 1⋅10 -1⋅69 +6⋅ 10) = -1⋅69 +7⋅ 10 (=1)
10= 79-1⋅69	eingesetzt in die Zeile drüber:	1	= -1⋅69 +7⋅(79 -1⋅ 69) = -1⋅69 +7⋅79 -7⋅ 69) = 7⋅79 -8⋅ 69 (=1)

Es gilt also: ggt(79,69)=1 = 7⋅79 -8⋅69

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

1 -7⋅79 = -8⋅69

-8⋅69 = -7⋅79 + 1 |+79⋅69

-8⋅69 + 79⋅69 = -7⋅79 + 79⋅69 + 1

(-8 + 79) ⋅ 69 = (-7 + 69) ⋅ 79 + 1

71⋅69 = 62⋅79 + 1

Es gilt also: 71⋅69 = 62⋅79 +1

Somit 71⋅69 = 1 mod 79

71 ist also das Inverse von 69 mod 79