Um längere Rechnungen zu vermeiden, rechnen wir:

(3003 - 602) mod 6 ≡ (3003 mod 6 - 602 mod 6) mod 6.

3003 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 3003 = 3000+3 = 6 ⋅ 500 +3.

602 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 602 = 600+2 = 6 ⋅ 100 +2.

Somit gilt:

(3003 - 602) mod 6 ≡ (3 - 2) mod 6 ≡ 1 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(80 ⋅ 70) mod 9 ≡ (80 mod 9 ⋅ 70 mod 9) mod 9.

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

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

Somit gilt:

(80 ⋅ 70) mod 9 ≡ (8 ⋅ 7) mod 9 ≡ 56 mod 9 ≡ 2 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: 216¹=216

2: 216²=216¹⁺¹=216¹⋅216¹ ≡ 216⋅216=46656 ≡ 10 mod 281

4: 216⁴=216²⁺²=216²⋅216² ≡ 10⋅10=100 ≡ 100 mod 281

8: 216⁸=216⁴⁺⁴=216⁴⋅216⁴ ≡ 100⋅100=10000 ≡ 165 mod 281

16: 216¹⁶=216⁸⁺⁸=216⁸⋅216⁸ ≡ 165⋅165=27225 ≡ 249 mod 281

32: 216³²=216¹⁶⁺¹⁶=216¹⁶⋅216¹⁶ ≡ 249⋅249=62001 ≡ 181 mod 281

64: 216⁶⁴=216³²⁺³²=216³²⋅216³² ≡ 181⋅181=32761 ≡ 165 mod 281

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

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

251 = 128+64+32+16+8+2+1

375²⁵¹

= 375^{128+64+32+16+8+2+1}

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

≡ 57 ⋅ 455 ⋅ 86 ⋅ 281 ⋅ 558 ⋅ 543 ⋅ 375 mod 631
≡ 25935 ⋅ 86 ⋅ 281 ⋅ 558 ⋅ 543 ⋅ 375 mod 631 ≡ 64 ⋅ 86 ⋅ 281 ⋅ 558 ⋅ 543 ⋅ 375 mod 631
≡ 5504 ⋅ 281 ⋅ 558 ⋅ 543 ⋅ 375 mod 631 ≡ 456 ⋅ 281 ⋅ 558 ⋅ 543 ⋅ 375 mod 631
≡ 128136 ⋅ 558 ⋅ 543 ⋅ 375 mod 631 ≡ 43 ⋅ 558 ⋅ 543 ⋅ 375 mod 631
≡ 23994 ⋅ 543 ⋅ 375 mod 631 ≡ 16 ⋅ 543 ⋅ 375 mod 631
≡ 8688 ⋅ 375 mod 631 ≡ 485 ⋅ 375 mod 631
≡ 181875 mod 631 ≡ 147 mod 631

Es gilt also: 375²⁵¹ ≡ 147 mod 631

Berechnung des größten gemeinsamen Teilers von 83 und 77

=>83	= 1⋅77 + 6
=>77	= 12⋅6 + 5
=>6	= 1⋅5 + 1
=>5	= 5⋅1 + 0

also gilt: ggt(83,77)=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= 6-1⋅5
5= 77-12⋅6	eingesetzt in die Zeile drüber:	1	= 1⋅6 -1⋅(77 -12⋅ 6) = 1⋅6 -1⋅77 +12⋅ 6) = -1⋅77 +13⋅ 6 (=1)
6= 83-1⋅77	eingesetzt in die Zeile drüber:	1	= -1⋅77 +13⋅(83 -1⋅ 77) = -1⋅77 +13⋅83 -13⋅ 77) = 13⋅83 -14⋅ 77 (=1)

Es gilt also: ggt(83,77)=1 = 13⋅83 -14⋅77

oder wenn man 13⋅83 auf die linke Seite bringt:

1 -13⋅83 = -14⋅77

-14⋅77 = -13⋅83 + 1 |+83⋅77

-14⋅77 + 83⋅77 = -13⋅83 + 83⋅77 + 1

(-14 + 83) ⋅ 77 = (-13 + 77) ⋅ 83 + 1

69⋅77 = 64⋅83 + 1

Es gilt also: 69⋅77 = 64⋅83 +1

Somit 69⋅77 = 1 mod 83

69 ist also das Inverse von 77 mod 83