Um längere Rechnungen zu vermeiden, rechnen wir:

(1200 + 2402) mod 6 ≡ (1200 mod 6 + 2402 mod 6) mod 6.

1200 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 1200 = 1200+0 = 6 ⋅ 200 +0.

2402 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 2402 = 2400+2 = 6 ⋅ 400 +2.

Somit gilt:

(1200 + 2402) mod 6 ≡ (0 + 2) mod 6 ≡ 2 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(63 ⋅ 28) mod 3 ≡ (63 mod 3 ⋅ 28 mod 3) mod 3.

63 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 63 = 63 + 0 = 21 ⋅ 3 + 0 ist.

28 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 28 = 27 + 1 = 9 ⋅ 3 + 1 ist.

Somit gilt:

(63 ⋅ 28) mod 3 ≡ (0 ⋅ 1) mod 3 ≡ 0 mod 3.

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

2: 231²=231¹⁺¹=231¹⋅231¹ ≡ 231⋅231=53361 ≡ 123 mod 467

4: 231⁴=231²⁺²=231²⋅231² ≡ 123⋅123=15129 ≡ 185 mod 467

8: 231⁸=231⁴⁺⁴=231⁴⋅231⁴ ≡ 185⋅185=34225 ≡ 134 mod 467

16: 231¹⁶=231⁸⁺⁸=231⁸⋅231⁸ ≡ 134⋅134=17956 ≡ 210 mod 467

32: 231³²=231¹⁶⁺¹⁶=231¹⁶⋅231¹⁶ ≡ 210⋅210=44100 ≡ 202 mod 467

64: 231⁶⁴=231³²⁺³²=231³²⋅231³² ≡ 202⋅202=40804 ≡ 175 mod 467

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

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

111 = 64+32+8+4+2+1

385¹¹¹

= 385^{64+32+8+4+2+1}

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

≡ 507 ⋅ 131 ⋅ 244 ⋅ 413 ⋅ 610 ⋅ 385 mod 757
≡ 66417 ⋅ 244 ⋅ 413 ⋅ 610 ⋅ 385 mod 757 ≡ 558 ⋅ 244 ⋅ 413 ⋅ 610 ⋅ 385 mod 757
≡ 136152 ⋅ 413 ⋅ 610 ⋅ 385 mod 757 ≡ 649 ⋅ 413 ⋅ 610 ⋅ 385 mod 757
≡ 268037 ⋅ 610 ⋅ 385 mod 757 ≡ 59 ⋅ 610 ⋅ 385 mod 757
≡ 35990 ⋅ 385 mod 757 ≡ 411 ⋅ 385 mod 757
≡ 158235 mod 757 ≡ 22 mod 757

Es gilt also: 385¹¹¹ ≡ 22 mod 757

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

=>101	= 1⋅98 + 3
=>98	= 32⋅3 + 2
=>3	= 1⋅2 + 1
=>2	= 2⋅1 + 0

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

Es gilt also: ggt(101,98)=1 = 33⋅101 -34⋅98

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

1 -33⋅101 = -34⋅98

-34⋅98 = -33⋅101 + 1 |+101⋅98

-34⋅98 + 101⋅98 = -33⋅101 + 101⋅98 + 1

(-34 + 101) ⋅ 98 = (-33 + 98) ⋅ 101 + 1

67⋅98 = 65⋅101 + 1

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

Somit 67⋅98 = 1 mod 101

67 ist also das Inverse von 98 mod 101