Um längere Rechnungen zu vermeiden, rechnen wir:

(1400 - 280) mod 7 ≡ (1400 mod 7 - 280 mod 7) mod 7.

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

280 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 280 = 280+0 = 7 ⋅ 40 +0.

Somit gilt:

(1400 - 280) mod 7 ≡ (0 - 0) mod 7 ≡ 0 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(86 ⋅ 88) mod 8 ≡ (86 mod 8 ⋅ 88 mod 8) mod 8.

86 mod 8 ≡ 6 mod 8 kann man relativ leicht bestimmen, weil ja 86 = 80 + 6 = 10 ⋅ 8 + 6 ist.

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

Somit gilt:

(86 ⋅ 88) mod 8 ≡ (6 ⋅ 0) mod 8 ≡ 0 mod 8.

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

2: 437²=437¹⁺¹=437¹⋅437¹ ≡ 437⋅437=190969 ≡ 499 mod 907

4: 437⁴=437²⁺²=437²⋅437² ≡ 499⋅499=249001 ≡ 483 mod 907

8: 437⁸=437⁴⁺⁴=437⁴⋅437⁴ ≡ 483⋅483=233289 ≡ 190 mod 907

16: 437¹⁶=437⁸⁺⁸=437⁸⋅437⁸ ≡ 190⋅190=36100 ≡ 727 mod 907

32: 437³²=437¹⁶⁺¹⁶=437¹⁶⋅437¹⁶ ≡ 727⋅727=528529 ≡ 655 mod 907

64: 437⁶⁴=437³²⁺³²=437³²⋅437³² ≡ 655⋅655=429025 ≡ 14 mod 907

128: 437¹²⁸=437⁶⁴⁺⁶⁴=437⁶⁴⋅437⁶⁴ ≡ 14⋅14=196 ≡ 196 mod 907

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

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

254 = 128+64+32+16+8+4+2

446²⁵⁴

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

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

≡ 13 ⋅ 784 ⋅ 28 ⋅ 513 ⋅ 91 ⋅ 872 ⋅ 832 mod 971
≡ 10192 ⋅ 28 ⋅ 513 ⋅ 91 ⋅ 872 ⋅ 832 mod 971 ≡ 482 ⋅ 28 ⋅ 513 ⋅ 91 ⋅ 872 ⋅ 832 mod 971
≡ 13496 ⋅ 513 ⋅ 91 ⋅ 872 ⋅ 832 mod 971 ≡ 873 ⋅ 513 ⋅ 91 ⋅ 872 ⋅ 832 mod 971
≡ 447849 ⋅ 91 ⋅ 872 ⋅ 832 mod 971 ≡ 218 ⋅ 91 ⋅ 872 ⋅ 832 mod 971
≡ 19838 ⋅ 872 ⋅ 832 mod 971 ≡ 418 ⋅ 872 ⋅ 832 mod 971
≡ 364496 ⋅ 832 mod 971 ≡ 371 ⋅ 832 mod 971
≡ 308672 mod 971 ≡ 865 mod 971

Es gilt also: 446²⁵⁴ ≡ 865 mod 971

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

=>97	= 2⋅34 + 29
=>34	= 1⋅29 + 5
=>29	= 5⋅5 + 4
=>5	= 1⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(97,34)=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= 5-1⋅4
4= 29-5⋅5	eingesetzt in die Zeile drüber:	1	= 1⋅5 -1⋅(29 -5⋅ 5) = 1⋅5 -1⋅29 +5⋅ 5) = -1⋅29 +6⋅ 5 (=1)
5= 34-1⋅29	eingesetzt in die Zeile drüber:	1	= -1⋅29 +6⋅(34 -1⋅ 29) = -1⋅29 +6⋅34 -6⋅ 29) = 6⋅34 -7⋅ 29 (=1)
29= 97-2⋅34	eingesetzt in die Zeile drüber:	1	= 6⋅34 -7⋅(97 -2⋅ 34) = 6⋅34 -7⋅97 +14⋅ 34) = -7⋅97 +20⋅ 34 (=1)

Es gilt also: ggt(97,34)=1 = -7⋅97 +20⋅34

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

1 +7⋅97 = +20⋅34

Es gilt also: 20⋅34 = 7⋅97 +1

Somit 20⋅34 = 1 mod 97

20 ist also das Inverse von 34 mod 97