Um längere Rechnungen zu vermeiden, rechnen wir:

(897 + 2998) mod 3 ≡ (897 mod 3 + 2998 mod 3) mod 3.

897 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 897 = 900-3 = 3 ⋅ 300 -3 = 3 ⋅ 300 - 3 + 0.

2998 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 2998 = 3000-2 = 3 ⋅ 1000 -2 = 3 ⋅ 1000 - 3 + 1.

Somit gilt:

(897 + 2998) mod 3 ≡ (0 + 1) mod 3 ≡ 1 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(58 ⋅ 56) mod 11 ≡ (58 mod 11 ⋅ 56 mod 11) mod 11.

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

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

Somit gilt:

(58 ⋅ 56) mod 11 ≡ (3 ⋅ 1) mod 11 ≡ 3 mod 11.

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

2: 606²=606¹⁺¹=606¹⋅606¹ ≡ 606⋅606=367236 ≡ 387 mod 647

4: 606⁴=606²⁺²=606²⋅606² ≡ 387⋅387=149769 ≡ 312 mod 647

8: 606⁸=606⁴⁺⁴=606⁴⋅606⁴ ≡ 312⋅312=97344 ≡ 294 mod 647

16: 606¹⁶=606⁸⁺⁸=606⁸⋅606⁸ ≡ 294⋅294=86436 ≡ 385 mod 647

32: 606³²=606¹⁶⁺¹⁶=606¹⁶⋅606¹⁶ ≡ 385⋅385=148225 ≡ 62 mod 647

64: 606⁶⁴=606³²⁺³²=606³²⋅606³² ≡ 62⋅62=3844 ≡ 609 mod 647

128: 606¹²⁸=606⁶⁴⁺⁶⁴=606⁶⁴⋅606⁶⁴ ≡ 609⋅609=370881 ≡ 150 mod 647

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

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

245 = 128+64+32+16+4+1

542²⁴⁵

= 542^{128+64+32+16+4+1}

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

≡ 211 ⋅ 761 ⋅ 40 ⋅ 658 ⋅ 411 ⋅ 542 mod 839
≡ 160571 ⋅ 40 ⋅ 658 ⋅ 411 ⋅ 542 mod 839 ≡ 322 ⋅ 40 ⋅ 658 ⋅ 411 ⋅ 542 mod 839
≡ 12880 ⋅ 658 ⋅ 411 ⋅ 542 mod 839 ≡ 295 ⋅ 658 ⋅ 411 ⋅ 542 mod 839
≡ 194110 ⋅ 411 ⋅ 542 mod 839 ≡ 301 ⋅ 411 ⋅ 542 mod 839
≡ 123711 ⋅ 542 mod 839 ≡ 378 ⋅ 542 mod 839
≡ 204876 mod 839 ≡ 160 mod 839

Es gilt also: 542²⁴⁵ ≡ 160 mod 839

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

=>73	= 1⋅52 + 21
=>52	= 2⋅21 + 10
=>21	= 2⋅10 + 1
=>10	= 10⋅1 + 0

also gilt: ggt(73,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= 21-2⋅10
10= 52-2⋅21	eingesetzt in die Zeile drüber:	1	= 1⋅21 -2⋅(52 -2⋅ 21) = 1⋅21 -2⋅52 +4⋅ 21) = -2⋅52 +5⋅ 21 (=1)
21= 73-1⋅52	eingesetzt in die Zeile drüber:	1	= -2⋅52 +5⋅(73 -1⋅ 52) = -2⋅52 +5⋅73 -5⋅ 52) = 5⋅73 -7⋅ 52 (=1)

Es gilt also: ggt(73,52)=1 = 5⋅73 -7⋅52

oder wenn man 5⋅73 auf die linke Seite bringt:

1 -5⋅73 = -7⋅52

-7⋅52 = -5⋅73 + 1 |+73⋅52

-7⋅52 + 73⋅52 = -5⋅73 + 73⋅52 + 1

(-7 + 73) ⋅ 52 = (-5 + 52) ⋅ 73 + 1

66⋅52 = 47⋅73 + 1

Es gilt also: 66⋅52 = 47⋅73 +1

Somit 66⋅52 = 1 mod 73

66 ist also das Inverse von 52 mod 73