Um längere Rechnungen zu vermeiden, rechnen wir:

(3000 - 1201) mod 3 ≡ (3000 mod 3 - 1201 mod 3) mod 3.

3000 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 3000 = 3000+0 = 3 ⋅ 1000 +0.

1201 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 1201 = 1200+1 = 3 ⋅ 400 +1.

Somit gilt:

(3000 - 1201) mod 3 ≡ (0 - 1) mod 3 ≡ -1 mod 3 ≡ 2 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(21 ⋅ 69) mod 11 ≡ (21 mod 11 ⋅ 69 mod 11) mod 11.

21 mod 11 ≡ 10 mod 11 kann man relativ leicht bestimmen, weil ja 21 = 11 + 10 = 1 ⋅ 11 + 10 ist.

69 mod 11 ≡ 3 mod 11 kann man relativ leicht bestimmen, weil ja 69 = 66 + 3 = 6 ⋅ 11 + 3 ist.

Somit gilt:

(21 ⋅ 69) mod 11 ≡ (10 ⋅ 3) mod 11 ≡ 30 mod 11 ≡ 8 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: 780¹=780

2: 780²=780¹⁺¹=780¹⋅780¹ ≡ 780⋅780=608400 ≡ 710 mod 907

4: 780⁴=780²⁺²=780²⋅780² ≡ 710⋅710=504100 ≡ 715 mod 907

8: 780⁸=780⁴⁺⁴=780⁴⋅780⁴ ≡ 715⋅715=511225 ≡ 584 mod 907

16: 780¹⁶=780⁸⁺⁸=780⁸⋅780⁸ ≡ 584⋅584=341056 ≡ 24 mod 907

32: 780³²=780¹⁶⁺¹⁶=780¹⁶⋅780¹⁶ ≡ 24⋅24=576 ≡ 576 mod 907

64: 780⁶⁴=780³²⁺³²=780³²⋅780³² ≡ 576⋅576=331776 ≡ 721 mod 907

128: 780¹²⁸=780⁶⁴⁺⁶⁴=780⁶⁴⋅780⁶⁴ ≡ 721⋅721=519841 ≡ 130 mod 907

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

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

207 = 128+64+8+4+2+1

302²⁰⁷

= 302^{128+64+8+4+2+1}

= 302¹²⁸⋅302⁶⁴⋅302⁸⋅302⁴⋅302²⋅302¹

≡ 261 ⋅ 568 ⋅ 871 ⋅ 232 ⋅ 162 ⋅ 302 mod 929
≡ 148248 ⋅ 871 ⋅ 232 ⋅ 162 ⋅ 302 mod 929 ≡ 537 ⋅ 871 ⋅ 232 ⋅ 162 ⋅ 302 mod 929
≡ 467727 ⋅ 232 ⋅ 162 ⋅ 302 mod 929 ≡ 440 ⋅ 232 ⋅ 162 ⋅ 302 mod 929
≡ 102080 ⋅ 162 ⋅ 302 mod 929 ≡ 819 ⋅ 162 ⋅ 302 mod 929
≡ 132678 ⋅ 302 mod 929 ≡ 760 ⋅ 302 mod 929
≡ 229520 mod 929 ≡ 57 mod 929

Es gilt also: 302²⁰⁷ ≡ 57 mod 929

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

=>101	= 1⋅67 + 34
=>67	= 1⋅34 + 33
=>34	= 1⋅33 + 1
=>33	= 33⋅1 + 0

also gilt: ggt(101,67)=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= 34-1⋅33
33= 67-1⋅34	eingesetzt in die Zeile drüber:	1	= 1⋅34 -1⋅(67 -1⋅ 34) = 1⋅34 -1⋅67 +1⋅ 34) = -1⋅67 +2⋅ 34 (=1)
34= 101-1⋅67	eingesetzt in die Zeile drüber:	1	= -1⋅67 +2⋅(101 -1⋅ 67) = -1⋅67 +2⋅101 -2⋅ 67) = 2⋅101 -3⋅ 67 (=1)

Es gilt also: ggt(101,67)=1 = 2⋅101 -3⋅67

oder wenn man 2⋅101 auf die linke Seite bringt:

1 -2⋅101 = -3⋅67

-3⋅67 = -2⋅101 + 1 |+101⋅67

-3⋅67 + 101⋅67 = -2⋅101 + 101⋅67 + 1

(-3 + 101) ⋅ 67 = (-2 + 67) ⋅ 101 + 1

98⋅67 = 65⋅101 + 1

Es gilt also: 98⋅67 = 65⋅101 +1

Somit 98⋅67 = 1 mod 101

98 ist also das Inverse von 67 mod 101