Um längere Rechnungen zu vermeiden, rechnen wir:

(802 + 39998) mod 8 ≡ (802 mod 8 + 39998 mod 8) mod 8.

802 mod 8 ≡ 2 mod 8 kann man relativ leicht bestimmen, weil ja 802 = 800+2 = 8 ⋅ 100 +2.

39998 mod 8 ≡ 6 mod 8 kann man relativ leicht bestimmen, weil ja 39998 = 39000+998 = 8 ⋅ 4875 +998.

Somit gilt:

(802 + 39998) mod 8 ≡ (2 + 6) mod 8 ≡ 8 mod 8 ≡ 0 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(73 ⋅ 88) mod 9 ≡ (73 mod 9 ⋅ 88 mod 9) mod 9.

73 mod 9 ≡ 1 mod 9 kann man relativ leicht bestimmen, weil ja 73 = 72 + 1 = 8 ⋅ 9 + 1 ist.

88 mod 9 ≡ 7 mod 9 kann man relativ leicht bestimmen, weil ja 88 = 81 + 7 = 9 ⋅ 9 + 7 ist.

Somit gilt:

(73 ⋅ 88) mod 9 ≡ (1 ⋅ 7) mod 9 ≡ 7 mod 9.

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

2: 542²=542¹⁺¹=542¹⋅542¹ ≡ 542⋅542=293764 ≡ 608 mod 883

4: 542⁴=542²⁺²=542²⋅542² ≡ 608⋅608=369664 ≡ 570 mod 883

8: 542⁸=542⁴⁺⁴=542⁴⋅542⁴ ≡ 570⋅570=324900 ≡ 839 mod 883

16: 542¹⁶=542⁸⁺⁸=542⁸⋅542⁸ ≡ 839⋅839=703921 ≡ 170 mod 883

32: 542³²=542¹⁶⁺¹⁶=542¹⁶⋅542¹⁶ ≡ 170⋅170=28900 ≡ 644 mod 883

64: 542⁶⁴=542³²⁺³²=542³²⋅542³² ≡ 644⋅644=414736 ≡ 609 mod 883

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

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

249 = 128+64+32+16+8+1

171²⁴⁹

= 171^{128+64+32+16+8+1}

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

≡ 305 ⋅ 204 ⋅ 104 ⋅ 56 ⋅ 314 ⋅ 171 mod 379
≡ 62220 ⋅ 104 ⋅ 56 ⋅ 314 ⋅ 171 mod 379 ≡ 64 ⋅ 104 ⋅ 56 ⋅ 314 ⋅ 171 mod 379
≡ 6656 ⋅ 56 ⋅ 314 ⋅ 171 mod 379 ≡ 213 ⋅ 56 ⋅ 314 ⋅ 171 mod 379
≡ 11928 ⋅ 314 ⋅ 171 mod 379 ≡ 179 ⋅ 314 ⋅ 171 mod 379
≡ 56206 ⋅ 171 mod 379 ≡ 114 ⋅ 171 mod 379
≡ 19494 mod 379 ≡ 165 mod 379

Es gilt also: 171²⁴⁹ ≡ 165 mod 379

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

=>97	= 1⋅52 + 45
=>52	= 1⋅45 + 7
=>45	= 6⋅7 + 3
=>7	= 2⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(97,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= 7-2⋅3
3= 45-6⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -2⋅(45 -6⋅ 7) = 1⋅7 -2⋅45 +12⋅ 7) = -2⋅45 +13⋅ 7 (=1)
7= 52-1⋅45	eingesetzt in die Zeile drüber:	1	= -2⋅45 +13⋅(52 -1⋅ 45) = -2⋅45 +13⋅52 -13⋅ 45) = 13⋅52 -15⋅ 45 (=1)
45= 97-1⋅52	eingesetzt in die Zeile drüber:	1	= 13⋅52 -15⋅(97 -1⋅ 52) = 13⋅52 -15⋅97 +15⋅ 52) = -15⋅97 +28⋅ 52 (=1)

Es gilt also: ggt(97,52)=1 = -15⋅97 +28⋅52

oder wenn man -15⋅97 auf die linke Seite bringt:

1 +15⋅97 = +28⋅52

Es gilt also: 28⋅52 = 15⋅97 +1

Somit 28⋅52 = 1 mod 97

28 ist also das Inverse von 52 mod 97