Um längere Rechnungen zu vermeiden, rechnen wir:

(3506 + 27996) mod 7 ≡ (3506 mod 7 + 27996 mod 7) mod 7.

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

27996 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 27996 = 28000-4 = 7 ⋅ 4000 -4 = 7 ⋅ 4000 - 7 + 3.

Somit gilt:

(3506 + 27996) mod 7 ≡ (6 + 3) mod 7 ≡ 9 mod 7 ≡ 2 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(68 ⋅ 44) mod 4 ≡ (68 mod 4 ⋅ 44 mod 4) mod 4.

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

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

Somit gilt:

(68 ⋅ 44) mod 4 ≡ (0 ⋅ 0) mod 4 ≡ 0 mod 4.

Die 8 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: 724¹=724

2: 724²=724¹⁺¹=724¹⋅724¹ ≡ 724⋅724=524176 ≡ 82 mod 773

4: 724⁴=724²⁺²=724²⋅724² ≡ 82⋅82=6724 ≡ 540 mod 773

8: 724⁸=724⁴⁺⁴=724⁴⋅724⁴ ≡ 540⋅540=291600 ≡ 179 mod 773

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

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

247 = 128+64+32+16+4+2+1

877²⁴⁷

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

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

≡ 177 ⋅ 319 ⋅ 118 ⋅ 816 ⋅ 49 ⋅ 900 ⋅ 877 mod 907
≡ 56463 ⋅ 118 ⋅ 816 ⋅ 49 ⋅ 900 ⋅ 877 mod 907 ≡ 229 ⋅ 118 ⋅ 816 ⋅ 49 ⋅ 900 ⋅ 877 mod 907
≡ 27022 ⋅ 816 ⋅ 49 ⋅ 900 ⋅ 877 mod 907 ≡ 719 ⋅ 816 ⋅ 49 ⋅ 900 ⋅ 877 mod 907
≡ 586704 ⋅ 49 ⋅ 900 ⋅ 877 mod 907 ≡ 782 ⋅ 49 ⋅ 900 ⋅ 877 mod 907
≡ 38318 ⋅ 900 ⋅ 877 mod 907 ≡ 224 ⋅ 900 ⋅ 877 mod 907
≡ 201600 ⋅ 877 mod 907 ≡ 246 ⋅ 877 mod 907
≡ 215742 mod 907 ≡ 783 mod 907

Es gilt also: 877²⁴⁷ ≡ 783 mod 907

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

=>97	= 1⋅88 + 9
=>88	= 9⋅9 + 7
=>9	= 1⋅7 + 2
=>7	= 3⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(97,88)=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= 7-3⋅2
2= 9-1⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -3⋅(9 -1⋅ 7) = 1⋅7 -3⋅9 +3⋅ 7) = -3⋅9 +4⋅ 7 (=1)
7= 88-9⋅9	eingesetzt in die Zeile drüber:	1	= -3⋅9 +4⋅(88 -9⋅ 9) = -3⋅9 +4⋅88 -36⋅ 9) = 4⋅88 -39⋅ 9 (=1)
9= 97-1⋅88	eingesetzt in die Zeile drüber:	1	= 4⋅88 -39⋅(97 -1⋅ 88) = 4⋅88 -39⋅97 +39⋅ 88) = -39⋅97 +43⋅ 88 (=1)

Es gilt also: ggt(97,88)=1 = -39⋅97 +43⋅88

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

1 +39⋅97 = +43⋅88

Es gilt also: 43⋅88 = 39⋅97 +1

Somit 43⋅88 = 1 mod 97

43 ist also das Inverse von 88 mod 97