Um längere Rechnungen zu vermeiden, rechnen wir:

(792 - 801) mod 8 ≡ (792 mod 8 - 801 mod 8) mod 8.

792 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 792 = 800-8 = 8 ⋅ 100 -8 = 8 ⋅ 100 - 8 + 0.

801 mod 8 ≡ 1 mod 8 kann man relativ leicht bestimmen, weil ja 801 = 800+1 = 8 ⋅ 100 +1.

Somit gilt:

(792 - 801) mod 8 ≡ (0 - 1) mod 8 ≡ -1 mod 8 ≡ 7 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(90 ⋅ 38) mod 6 ≡ (90 mod 6 ⋅ 38 mod 6) mod 6.

90 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 90 = 90 + 0 = 15 ⋅ 6 + 0 ist.

38 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 38 = 36 + 2 = 6 ⋅ 6 + 2 ist.

Somit gilt:

(90 ⋅ 38) mod 6 ≡ (0 ⋅ 2) mod 6 ≡ 0 mod 6.

Die 32 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: 478¹=478

2: 478²=478¹⁺¹=478¹⋅478¹ ≡ 478⋅478=228484 ≡ 286 mod 521

4: 478⁴=478²⁺²=478²⋅478² ≡ 286⋅286=81796 ≡ 520 mod 521

8: 478⁸=478⁴⁺⁴=478⁴⋅478⁴ ≡ 520⋅520=270400 ≡ 1 mod 521

16: 478¹⁶=478⁸⁺⁸=478⁸⋅478⁸ ≡ 1⋅1=1 ≡ 1 mod 521

32: 478³²=478¹⁶⁺¹⁶=478¹⁶⋅478¹⁶ ≡ 1⋅1=1 ≡ 1 mod 521

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

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

175 = 128+32+8+4+2+1

408¹⁷⁵

= 408^{128+32+8+4+2+1}

= 408¹²⁸⋅408³²⋅408⁸⋅408⁴⋅408²⋅408¹

≡ 78 ⋅ 135 ⋅ 694 ⋅ 723 ⋅ 688 ⋅ 408 mod 797
≡ 10530 ⋅ 694 ⋅ 723 ⋅ 688 ⋅ 408 mod 797 ≡ 169 ⋅ 694 ⋅ 723 ⋅ 688 ⋅ 408 mod 797
≡ 117286 ⋅ 723 ⋅ 688 ⋅ 408 mod 797 ≡ 127 ⋅ 723 ⋅ 688 ⋅ 408 mod 797
≡ 91821 ⋅ 688 ⋅ 408 mod 797 ≡ 166 ⋅ 688 ⋅ 408 mod 797
≡ 114208 ⋅ 408 mod 797 ≡ 237 ⋅ 408 mod 797
≡ 96696 mod 797 ≡ 259 mod 797

Es gilt also: 408¹⁷⁵ ≡ 259 mod 797

Berechnung des größten gemeinsamen Teilers von 97 und 54

=>97	= 1⋅54 + 43
=>54	= 1⋅43 + 11
=>43	= 3⋅11 + 10
=>11	= 1⋅10 + 1
=>10	= 10⋅1 + 0

also gilt: ggt(97,54)=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= 11-1⋅10
10= 43-3⋅11	eingesetzt in die Zeile drüber:	1	= 1⋅11 -1⋅(43 -3⋅ 11) = 1⋅11 -1⋅43 +3⋅ 11) = -1⋅43 +4⋅ 11 (=1)
11= 54-1⋅43	eingesetzt in die Zeile drüber:	1	= -1⋅43 +4⋅(54 -1⋅ 43) = -1⋅43 +4⋅54 -4⋅ 43) = 4⋅54 -5⋅ 43 (=1)
43= 97-1⋅54	eingesetzt in die Zeile drüber:	1	= 4⋅54 -5⋅(97 -1⋅ 54) = 4⋅54 -5⋅97 +5⋅ 54) = -5⋅97 +9⋅ 54 (=1)

Es gilt also: ggt(97,54)=1 = -5⋅97 +9⋅54

oder wenn man -5⋅97 auf die linke Seite bringt:

1 +5⋅97 = +9⋅54

Es gilt also: 9⋅54 = 5⋅97 +1

Somit 9⋅54 = 1 mod 97

9 ist also das Inverse von 54 mod 97