Um längere Rechnungen zu vermeiden, rechnen wir:

(1402 - 3504) mod 7 ≡ (1402 mod 7 - 3504 mod 7) mod 7.

1402 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 1402 = 1400+2 = 7 ⋅ 200 +2.

3504 mod 7 ≡ 4 mod 7 kann man relativ leicht bestimmen, weil ja 3504 = 3500+4 = 7 ⋅ 500 +4.

Somit gilt:

(1402 - 3504) mod 7 ≡ (2 - 4) mod 7 ≡ -2 mod 7 ≡ 5 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(18 ⋅ 34) mod 10 ≡ (18 mod 10 ⋅ 34 mod 10) mod 10.

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

34 mod 10 ≡ 4 mod 10 kann man relativ leicht bestimmen, weil ja 34 = 30 + 4 = 3 ⋅ 10 + 4 ist.

Somit gilt:

(18 ⋅ 34) mod 10 ≡ (8 ⋅ 4) mod 10 ≡ 32 mod 10 ≡ 2 mod 10.

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

2: 322²=322¹⁺¹=322¹⋅322¹ ≡ 322⋅322=103684 ≡ 190 mod 367

4: 322⁴=322²⁺²=322²⋅322² ≡ 190⋅190=36100 ≡ 134 mod 367

8: 322⁸=322⁴⁺⁴=322⁴⋅322⁴ ≡ 134⋅134=17956 ≡ 340 mod 367

16: 322¹⁶=322⁸⁺⁸=322⁸⋅322⁸ ≡ 340⋅340=115600 ≡ 362 mod 367

32: 322³²=322¹⁶⁺¹⁶=322¹⁶⋅322¹⁶ ≡ 362⋅362=131044 ≡ 25 mod 367

64: 322⁶⁴=322³²⁺³²=322³²⋅322³² ≡ 25⋅25=625 ≡ 258 mod 367

128: 322¹²⁸=322⁶⁴⁺⁶⁴=322⁶⁴⋅322⁶⁴ ≡ 258⋅258=66564 ≡ 137 mod 367

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

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

159 = 128+16+8+4+2+1

242¹⁵⁹

= 242^{128+16+8+4+2+1}

= 242¹²⁸⋅242¹⁶⋅242⁸⋅242⁴⋅242²⋅242¹

≡ 513 ⋅ 458 ⋅ 388 ⋅ 600 ⋅ 610 ⋅ 242 mod 743
≡ 234954 ⋅ 388 ⋅ 600 ⋅ 610 ⋅ 242 mod 743 ≡ 166 ⋅ 388 ⋅ 600 ⋅ 610 ⋅ 242 mod 743
≡ 64408 ⋅ 600 ⋅ 610 ⋅ 242 mod 743 ≡ 510 ⋅ 600 ⋅ 610 ⋅ 242 mod 743
≡ 306000 ⋅ 610 ⋅ 242 mod 743 ≡ 627 ⋅ 610 ⋅ 242 mod 743
≡ 382470 ⋅ 242 mod 743 ≡ 568 ⋅ 242 mod 743
≡ 137456 mod 743 ≡ 1 mod 743

Es gilt also: 242¹⁵⁹ ≡ 1 mod 743

Berechnung des größten gemeinsamen Teilers von 61 und 19

=>61	= 3⋅19 + 4
=>19	= 4⋅4 + 3
=>4	= 1⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(61,19)=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= 4-1⋅3
3= 19-4⋅4	eingesetzt in die Zeile drüber:	1	= 1⋅4 -1⋅(19 -4⋅ 4) = 1⋅4 -1⋅19 +4⋅ 4) = -1⋅19 +5⋅ 4 (=1)
4= 61-3⋅19	eingesetzt in die Zeile drüber:	1	= -1⋅19 +5⋅(61 -3⋅ 19) = -1⋅19 +5⋅61 -15⋅ 19) = 5⋅61 -16⋅ 19 (=1)

Es gilt also: ggt(61,19)=1 = 5⋅61 -16⋅19

oder wenn man 5⋅61 auf die linke Seite bringt:

1 -5⋅61 = -16⋅19

-16⋅19 = -5⋅61 + 1 |+61⋅19

-16⋅19 + 61⋅19 = -5⋅61 + 61⋅19 + 1

(-16 + 61) ⋅ 19 = (-5 + 19) ⋅ 61 + 1

45⋅19 = 14⋅61 + 1

Es gilt also: 45⋅19 = 14⋅61 +1

Somit 45⋅19 = 1 mod 61

45 ist also das Inverse von 19 mod 61