Um längere Rechnungen zu vermeiden, rechnen wir:

(27004 - 184) mod 9 ≡ (27004 mod 9 - 184 mod 9) mod 9.

27004 mod 9 ≡ 4 mod 9 kann man relativ leicht bestimmen, weil ja 27004 = 27000+4 = 9 ⋅ 3000 +4.

184 mod 9 ≡ 4 mod 9 kann man relativ leicht bestimmen, weil ja 184 = 180+4 = 9 ⋅ 20 +4.

Somit gilt:

(27004 - 184) mod 9 ≡ (4 - 4) mod 9 ≡ 0 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(73 ⋅ 96) mod 6 ≡ (73 mod 6 ⋅ 96 mod 6) mod 6.

73 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 73 = 72 + 1 = 12 ⋅ 6 + 1 ist.

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

Somit gilt:

(73 ⋅ 96) mod 6 ≡ (1 ⋅ 0) mod 6 ≡ 0 mod 6.

Die 64 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: 320¹=320

2: 320²=320¹⁺¹=320¹⋅320¹ ≡ 320⋅320=102400 ≡ 265 mod 619

4: 320⁴=320²⁺²=320²⋅320² ≡ 265⋅265=70225 ≡ 278 mod 619

8: 320⁸=320⁴⁺⁴=320⁴⋅320⁴ ≡ 278⋅278=77284 ≡ 528 mod 619

16: 320¹⁶=320⁸⁺⁸=320⁸⋅320⁸ ≡ 528⋅528=278784 ≡ 234 mod 619

32: 320³²=320¹⁶⁺¹⁶=320¹⁶⋅320¹⁶ ≡ 234⋅234=54756 ≡ 284 mod 619

64: 320⁶⁴=320³²⁺³²=320³²⋅320³² ≡ 284⋅284=80656 ≡ 186 mod 619

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

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

115 = 64+32+16+2+1

317¹¹⁵

= 317^64+32+16+2+1

= 317⁶⁴⋅317³²⋅317¹⁶⋅317²⋅317¹

≡ 17 ⋅ 363 ⋅ 217 ⋅ 143 ⋅ 317 mod 383
≡ 6171 ⋅ 217 ⋅ 143 ⋅ 317 mod 383 ≡ 43 ⋅ 217 ⋅ 143 ⋅ 317 mod 383
≡ 9331 ⋅ 143 ⋅ 317 mod 383 ≡ 139 ⋅ 143 ⋅ 317 mod 383
≡ 19877 ⋅ 317 mod 383 ≡ 344 ⋅ 317 mod 383
≡ 109048 mod 383 ≡ 276 mod 383

Es gilt also: 317¹¹⁵ ≡ 276 mod 383

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

=>97	= 1⋅86 + 11
=>86	= 7⋅11 + 9
=>11	= 1⋅9 + 2
=>9	= 4⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(97,86)=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-4⋅2
2= 11-1⋅9	eingesetzt in die Zeile drüber:	1	= 1⋅9 -4⋅(11 -1⋅ 9) = 1⋅9 -4⋅11 +4⋅ 9) = -4⋅11 +5⋅ 9 (=1)
9= 86-7⋅11	eingesetzt in die Zeile drüber:	1	= -4⋅11 +5⋅(86 -7⋅ 11) = -4⋅11 +5⋅86 -35⋅ 11) = 5⋅86 -39⋅ 11 (=1)
11= 97-1⋅86	eingesetzt in die Zeile drüber:	1	= 5⋅86 -39⋅(97 -1⋅ 86) = 5⋅86 -39⋅97 +39⋅ 86) = -39⋅97 +44⋅ 86 (=1)

Es gilt also: ggt(97,86)=1 = -39⋅97 +44⋅86

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

1 +39⋅97 = +44⋅86

Es gilt also: 44⋅86 = 39⋅97 +1

Somit 44⋅86 = 1 mod 97

44 ist also das Inverse von 86 mod 97