Um längere Rechnungen zu vermeiden, rechnen wir:

(119 - 3006) mod 6 ≡ (119 mod 6 - 3006 mod 6) mod 6.

119 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 119 = 120-1 = 6 ⋅ 20 -1 = 6 ⋅ 20 - 6 + 5.

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

Somit gilt:

(119 - 3006) mod 6 ≡ (5 - 0) mod 6 ≡ 5 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(28 ⋅ 59) mod 7 ≡ (28 mod 7 ⋅ 59 mod 7) mod 7.

28 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 28 = 28 + 0 = 4 ⋅ 7 + 0 ist.

59 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 59 = 56 + 3 = 8 ⋅ 7 + 3 ist.

Somit gilt:

(28 ⋅ 59) mod 7 ≡ (0 ⋅ 3) mod 7 ≡ 0 mod 7.

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

2: 146²=146¹⁺¹=146¹⋅146¹ ≡ 146⋅146=21316 ≡ 178 mod 271

4: 146⁴=146²⁺²=146²⋅146² ≡ 178⋅178=31684 ≡ 248 mod 271

8: 146⁸=146⁴⁺⁴=146⁴⋅146⁴ ≡ 248⋅248=61504 ≡ 258 mod 271

16: 146¹⁶=146⁸⁺⁸=146⁸⋅146⁸ ≡ 258⋅258=66564 ≡ 169 mod 271

32: 146³²=146¹⁶⁺¹⁶=146¹⁶⋅146¹⁶ ≡ 169⋅169=28561 ≡ 106 mod 271

64: 146⁶⁴=146³²⁺³²=146³²⋅146³² ≡ 106⋅106=11236 ≡ 125 mod 271

128: 146¹²⁸=146⁶⁴⁺⁶⁴=146⁶⁴⋅146⁶⁴ ≡ 125⋅125=15625 ≡ 178 mod 271

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

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

181 = 128+32+16+4+1

562¹⁸¹

= 562^{128+32+16+4+1}

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

≡ 516 ⋅ 738 ⋅ 741 ⋅ 494 ⋅ 562 mod 883
≡ 380808 ⋅ 741 ⋅ 494 ⋅ 562 mod 883 ≡ 235 ⋅ 741 ⋅ 494 ⋅ 562 mod 883
≡ 174135 ⋅ 494 ⋅ 562 mod 883 ≡ 184 ⋅ 494 ⋅ 562 mod 883
≡ 90896 ⋅ 562 mod 883 ≡ 830 ⋅ 562 mod 883
≡ 466460 mod 883 ≡ 236 mod 883

Es gilt also: 562¹⁸¹ ≡ 236 mod 883

Berechnung des größten gemeinsamen Teilers von 89 und 27

=>89	= 3⋅27 + 8
=>27	= 3⋅8 + 3
=>8	= 2⋅3 + 2
=>3	= 1⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(89,27)=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= 8-2⋅3	eingesetzt in die Zeile drüber:	1	= 1⋅3 -1⋅(8 -2⋅ 3) = 1⋅3 -1⋅8 +2⋅ 3) = -1⋅8 +3⋅ 3 (=1)
3= 27-3⋅8	eingesetzt in die Zeile drüber:	1	= -1⋅8 +3⋅(27 -3⋅ 8) = -1⋅8 +3⋅27 -9⋅ 8) = 3⋅27 -10⋅ 8 (=1)
8= 89-3⋅27	eingesetzt in die Zeile drüber:	1	= 3⋅27 -10⋅(89 -3⋅ 27) = 3⋅27 -10⋅89 +30⋅ 27) = -10⋅89 +33⋅ 27 (=1)

Es gilt also: ggt(89,27)=1 = -10⋅89 +33⋅27

oder wenn man -10⋅89 auf die linke Seite bringt:

1 +10⋅89 = +33⋅27

Es gilt also: 33⋅27 = 10⋅89 +1

Somit 33⋅27 = 1 mod 89

33 ist also das Inverse von 27 mod 89