Um längere Rechnungen zu vermeiden, rechnen wir:

(12002 - 114) mod 6 ≡ (12002 mod 6 - 114 mod 6) mod 6.

12002 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 12002 = 12000+2 = 6 ⋅ 2000 +2.

114 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 114 = 120-6 = 6 ⋅ 20 -6 = 6 ⋅ 20 - 6 + 0.

Somit gilt:

(12002 - 114) mod 6 ≡ (2 - 0) mod 6 ≡ 2 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(99 ⋅ 66) mod 5 ≡ (99 mod 5 ⋅ 66 mod 5) mod 5.

99 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 99 = 95 + 4 = 19 ⋅ 5 + 4 ist.

66 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 66 = 65 + 1 = 13 ⋅ 5 + 1 ist.

Somit gilt:

(99 ⋅ 66) mod 5 ≡ (4 ⋅ 1) mod 5 ≡ 4 mod 5.

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

2: 363²=363¹⁺¹=363¹⋅363¹ ≡ 363⋅363=131769 ≡ 500 mod 881

4: 363⁴=363²⁺²=363²⋅363² ≡ 500⋅500=250000 ≡ 677 mod 881

8: 363⁸=363⁴⁺⁴=363⁴⋅363⁴ ≡ 677⋅677=458329 ≡ 209 mod 881

16: 363¹⁶=363⁸⁺⁸=363⁸⋅363⁸ ≡ 209⋅209=43681 ≡ 512 mod 881

32: 363³²=363¹⁶⁺¹⁶=363¹⁶⋅363¹⁶ ≡ 512⋅512=262144 ≡ 487 mod 881

64: 363⁶⁴=363³²⁺³²=363³²⋅363³² ≡ 487⋅487=237169 ≡ 180 mod 881

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

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

62 = 32+16+8+4+2

311⁶²

= 311^32+16+8+4+2

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

≡ 85 ⋅ 46 ⋅ 576 ⋅ 653 ⋅ 587 mod 677
≡ 3910 ⋅ 576 ⋅ 653 ⋅ 587 mod 677 ≡ 525 ⋅ 576 ⋅ 653 ⋅ 587 mod 677
≡ 302400 ⋅ 653 ⋅ 587 mod 677 ≡ 458 ⋅ 653 ⋅ 587 mod 677
≡ 299074 ⋅ 587 mod 677 ≡ 517 ⋅ 587 mod 677
≡ 303479 mod 677 ≡ 183 mod 677

Es gilt also: 311⁶² ≡ 183 mod 677

Berechnung des größten gemeinsamen Teilers von 101 und 48

=>101	= 2⋅48 + 5
=>48	= 9⋅5 + 3
=>5	= 1⋅3 + 2
=>3	= 1⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(101,48)=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= 3-1⋅2
2= 5-1⋅3	eingesetzt in die Zeile drüber:	1	= 1⋅3 -1⋅(5 -1⋅ 3) = 1⋅3 -1⋅5 +1⋅ 3) = -1⋅5 +2⋅ 3 (=1)
3= 48-9⋅5	eingesetzt in die Zeile drüber:	1	= -1⋅5 +2⋅(48 -9⋅ 5) = -1⋅5 +2⋅48 -18⋅ 5) = 2⋅48 -19⋅ 5 (=1)
5= 101-2⋅48	eingesetzt in die Zeile drüber:	1	= 2⋅48 -19⋅(101 -2⋅ 48) = 2⋅48 -19⋅101 +38⋅ 48) = -19⋅101 +40⋅ 48 (=1)

Es gilt also: ggt(101,48)=1 = -19⋅101 +40⋅48

oder wenn man -19⋅101 auf die linke Seite bringt:

1 +19⋅101 = +40⋅48

Es gilt also: 40⋅48 = 19⋅101 +1

Somit 40⋅48 = 1 mod 101

40 ist also das Inverse von 48 mod 101