Um längere Rechnungen zu vermeiden, rechnen wir:

(26994 + 86) mod 9 ≡ (26994 mod 9 + 86 mod 9) mod 9.

26994 mod 9 ≡ 3 mod 9 kann man relativ leicht bestimmen, weil ja 26994 = 27000-6 = 9 ⋅ 3000 -6 = 9 ⋅ 3000 - 9 + 3.

86 mod 9 ≡ 5 mod 9 kann man relativ leicht bestimmen, weil ja 86 = 90-4 = 9 ⋅ 10 -4 = 9 ⋅ 10 - 9 + 5.

Somit gilt:

(26994 + 86) mod 9 ≡ (3 + 5) mod 9 ≡ 8 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(98 ⋅ 91) mod 6 ≡ (98 mod 6 ⋅ 91 mod 6) mod 6.

98 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 98 = 96 + 2 = 16 ⋅ 6 + 2 ist.

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

Somit gilt:

(98 ⋅ 91) mod 6 ≡ (2 ⋅ 1) mod 6 ≡ 2 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: 265¹=265

2: 265²=265¹⁺¹=265¹⋅265¹ ≡ 265⋅265=70225 ≡ 250 mod 311

4: 265⁴=265²⁺²=265²⋅265² ≡ 250⋅250=62500 ≡ 300 mod 311

8: 265⁸=265⁴⁺⁴=265⁴⋅265⁴ ≡ 300⋅300=90000 ≡ 121 mod 311

16: 265¹⁶=265⁸⁺⁸=265⁸⋅265⁸ ≡ 121⋅121=14641 ≡ 24 mod 311

32: 265³²=265¹⁶⁺¹⁶=265¹⁶⋅265¹⁶ ≡ 24⋅24=576 ≡ 265 mod 311

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

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

223 = 128+64+16+8+4+2+1

793²²³

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

= 793¹²⁸⋅793⁶⁴⋅793¹⁶⋅793⁸⋅793⁴⋅793²⋅793¹

≡ 521 ⋅ 173 ⋅ 822 ⋅ 113 ⋅ 598 ⋅ 253 ⋅ 793 mod 919
≡ 90133 ⋅ 822 ⋅ 113 ⋅ 598 ⋅ 253 ⋅ 793 mod 919 ≡ 71 ⋅ 822 ⋅ 113 ⋅ 598 ⋅ 253 ⋅ 793 mod 919
≡ 58362 ⋅ 113 ⋅ 598 ⋅ 253 ⋅ 793 mod 919 ≡ 465 ⋅ 113 ⋅ 598 ⋅ 253 ⋅ 793 mod 919
≡ 52545 ⋅ 598 ⋅ 253 ⋅ 793 mod 919 ≡ 162 ⋅ 598 ⋅ 253 ⋅ 793 mod 919
≡ 96876 ⋅ 253 ⋅ 793 mod 919 ≡ 381 ⋅ 253 ⋅ 793 mod 919
≡ 96393 ⋅ 793 mod 919 ≡ 817 ⋅ 793 mod 919
≡ 647881 mod 919 ≡ 905 mod 919

Es gilt also: 793²²³ ≡ 905 mod 919

Berechnung des größten gemeinsamen Teilers von 71 und 62

=>71	= 1⋅62 + 9
=>62	= 6⋅9 + 8
=>9	= 1⋅8 + 1
=>8	= 8⋅1 + 0

also gilt: ggt(71,62)=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= 9-1⋅8
8= 62-6⋅9	eingesetzt in die Zeile drüber:	1	= 1⋅9 -1⋅(62 -6⋅ 9) = 1⋅9 -1⋅62 +6⋅ 9) = -1⋅62 +7⋅ 9 (=1)
9= 71-1⋅62	eingesetzt in die Zeile drüber:	1	= -1⋅62 +7⋅(71 -1⋅ 62) = -1⋅62 +7⋅71 -7⋅ 62) = 7⋅71 -8⋅ 62 (=1)

Es gilt also: ggt(71,62)=1 = 7⋅71 -8⋅62

oder wenn man 7⋅71 auf die linke Seite bringt:

1 -7⋅71 = -8⋅62

-8⋅62 = -7⋅71 + 1 |+71⋅62

-8⋅62 + 71⋅62 = -7⋅71 + 71⋅62 + 1

(-8 + 71) ⋅ 62 = (-7 + 62) ⋅ 71 + 1

63⋅62 = 55⋅71 + 1

Es gilt also: 63⋅62 = 55⋅71 +1

Somit 63⋅62 = 1 mod 71

63 ist also das Inverse von 62 mod 71