Um längere Rechnungen zu vermeiden, rechnen wir:

(306 + 12002) mod 6 ≡ (306 mod 6 + 12002 mod 6) mod 6.

306 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 306 = 300+6 = 6 ⋅ 50 +6.

12002 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 12002 = 12000+2 = 6 ⋅ 2000 +2.

Somit gilt:

(306 + 12002) mod 6 ≡ (0 + 2) mod 6 ≡ 2 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(58 ⋅ 53) mod 5 ≡ (58 mod 5 ⋅ 53 mod 5) mod 5.

58 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 58 = 55 + 3 = 11 ⋅ 5 + 3 ist.

53 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 53 = 50 + 3 = 10 ⋅ 5 + 3 ist.

Somit gilt:

(58 ⋅ 53) mod 5 ≡ (3 ⋅ 3) mod 5 ≡ 9 mod 5 ≡ 4 mod 5.

Die 16 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: 435¹=435

2: 435²=435¹⁺¹=435¹⋅435¹ ≡ 435⋅435=189225 ≡ 111 mod 733

4: 435⁴=435²⁺²=435²⋅435² ≡ 111⋅111=12321 ≡ 593 mod 733

8: 435⁸=435⁴⁺⁴=435⁴⋅435⁴ ≡ 593⋅593=351649 ≡ 542 mod 733

16: 435¹⁶=435⁸⁺⁸=435⁸⋅435⁸ ≡ 542⋅542=293764 ≡ 564 mod 733

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

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

255 = 128+64+32+16+8+4+2+1

416²⁵⁵

= 416^{128+64+32+16+8+4+2+1}

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

≡ 434 ⋅ 607 ⋅ 665 ⋅ 556 ⋅ 224 ⋅ 711 ⋅ 213 ⋅ 416 mod 827
≡ 263438 ⋅ 665 ⋅ 556 ⋅ 224 ⋅ 711 ⋅ 213 ⋅ 416 mod 827 ≡ 452 ⋅ 665 ⋅ 556 ⋅ 224 ⋅ 711 ⋅ 213 ⋅ 416 mod 827
≡ 300580 ⋅ 556 ⋅ 224 ⋅ 711 ⋅ 213 ⋅ 416 mod 827 ≡ 379 ⋅ 556 ⋅ 224 ⋅ 711 ⋅ 213 ⋅ 416 mod 827
≡ 210724 ⋅ 224 ⋅ 711 ⋅ 213 ⋅ 416 mod 827 ≡ 666 ⋅ 224 ⋅ 711 ⋅ 213 ⋅ 416 mod 827
≡ 149184 ⋅ 711 ⋅ 213 ⋅ 416 mod 827 ≡ 324 ⋅ 711 ⋅ 213 ⋅ 416 mod 827
≡ 230364 ⋅ 213 ⋅ 416 mod 827 ≡ 458 ⋅ 213 ⋅ 416 mod 827
≡ 97554 ⋅ 416 mod 827 ≡ 795 ⋅ 416 mod 827
≡ 330720 mod 827 ≡ 747 mod 827

Es gilt also: 416²⁵⁵ ≡ 747 mod 827

Berechnung des größten gemeinsamen Teilers von 73 und 59

=>73	= 1⋅59 + 14
=>59	= 4⋅14 + 3
=>14	= 4⋅3 + 2
=>3	= 1⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(73,59)=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= 14-4⋅3	eingesetzt in die Zeile drüber:	1	= 1⋅3 -1⋅(14 -4⋅ 3) = 1⋅3 -1⋅14 +4⋅ 3) = -1⋅14 +5⋅ 3 (=1)
3= 59-4⋅14	eingesetzt in die Zeile drüber:	1	= -1⋅14 +5⋅(59 -4⋅ 14) = -1⋅14 +5⋅59 -20⋅ 14) = 5⋅59 -21⋅ 14 (=1)
14= 73-1⋅59	eingesetzt in die Zeile drüber:	1	= 5⋅59 -21⋅(73 -1⋅ 59) = 5⋅59 -21⋅73 +21⋅ 59) = -21⋅73 +26⋅ 59 (=1)

Es gilt also: ggt(73,59)=1 = -21⋅73 +26⋅59

oder wenn man -21⋅73 auf die linke Seite bringt:

1 +21⋅73 = +26⋅59

Es gilt also: 26⋅59 = 21⋅73 +1

Somit 26⋅59 = 1 mod 73

26 ist also das Inverse von 59 mod 73