Um längere Rechnungen zu vermeiden, rechnen wir:

(2406 + 3195) mod 8 ≡ (2406 mod 8 + 3195 mod 8) mod 8.

2406 mod 8 ≡ 6 mod 8 kann man relativ leicht bestimmen, weil ja 2406 = 2400+6 = 8 ⋅ 300 +6.

3195 mod 8 ≡ 3 mod 8 kann man relativ leicht bestimmen, weil ja 3195 = 3200-5 = 8 ⋅ 400 -5 = 8 ⋅ 400 - 8 + 3.

Somit gilt:

(2406 + 3195) mod 8 ≡ (6 + 3) mod 8 ≡ 9 mod 8 ≡ 1 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(77 ⋅ 80) mod 7 ≡ (77 mod 7 ⋅ 80 mod 7) mod 7.

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

80 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 80 = 77 + 3 = 11 ⋅ 7 + 3 ist.

Somit gilt:

(77 ⋅ 80) 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: 255¹=255

2: 255²=255¹⁺¹=255¹⋅255¹ ≡ 255⋅255=65025 ≡ 369 mod 449

4: 255⁴=255²⁺²=255²⋅255² ≡ 369⋅369=136161 ≡ 114 mod 449

8: 255⁸=255⁴⁺⁴=255⁴⋅255⁴ ≡ 114⋅114=12996 ≡ 424 mod 449

16: 255¹⁶=255⁸⁺⁸=255⁸⋅255⁸ ≡ 424⋅424=179776 ≡ 176 mod 449

32: 255³²=255¹⁶⁺¹⁶=255¹⁶⋅255¹⁶ ≡ 176⋅176=30976 ≡ 444 mod 449

64: 255⁶⁴=255³²⁺³²=255³²⋅255³² ≡ 444⋅444=197136 ≡ 25 mod 449

128: 255¹²⁸=255⁶⁴⁺⁶⁴=255⁶⁴⋅255⁶⁴ ≡ 25⋅25=625 ≡ 176 mod 449

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

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

105 = 64+32+8+1

580¹⁰⁵

= 580^64+32+8+1

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

≡ 313 ⋅ 86 ⋅ 670 ⋅ 580 mod 787
≡ 26918 ⋅ 670 ⋅ 580 mod 787 ≡ 160 ⋅ 670 ⋅ 580 mod 787
≡ 107200 ⋅ 580 mod 787 ≡ 168 ⋅ 580 mod 787
≡ 97440 mod 787 ≡ 639 mod 787

Es gilt also: 580¹⁰⁵ ≡ 639 mod 787

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

=>89	= 1⋅86 + 3
=>86	= 28⋅3 + 2
=>3	= 1⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(89,86)=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= 86-28⋅3	eingesetzt in die Zeile drüber:	1	= 1⋅3 -1⋅(86 -28⋅ 3) = 1⋅3 -1⋅86 +28⋅ 3) = -1⋅86 +29⋅ 3 (=1)
3= 89-1⋅86	eingesetzt in die Zeile drüber:	1	= -1⋅86 +29⋅(89 -1⋅ 86) = -1⋅86 +29⋅89 -29⋅ 86) = 29⋅89 -30⋅ 86 (=1)

Es gilt also: ggt(89,86)=1 = 29⋅89 -30⋅86

oder wenn man 29⋅89 auf die linke Seite bringt:

1 -29⋅89 = -30⋅86

-30⋅86 = -29⋅89 + 1 |+89⋅86

-30⋅86 + 89⋅86 = -29⋅89 + 89⋅86 + 1

(-30 + 89) ⋅ 86 = (-29 + 86) ⋅ 89 + 1

59⋅86 = 57⋅89 + 1

Es gilt also: 59⋅86 = 57⋅89 +1

Somit 59⋅86 = 1 mod 89

59 ist also das Inverse von 86 mod 89