Um längere Rechnungen zu vermeiden, rechnen wir:

(26995 - 897) mod 9 ≡ (26995 mod 9 - 897 mod 9) mod 9.

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

897 mod 9 ≡ 6 mod 9 kann man relativ leicht bestimmen, weil ja 897 = 900-3 = 9 ⋅ 100 -3 = 9 ⋅ 100 - 9 + 6.

Somit gilt:

(26995 - 897) mod 9 ≡ (4 - 6) mod 9 ≡ -2 mod 9 ≡ 7 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

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

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

27 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 27 = 24 + 3 = 4 ⋅ 6 + 3 ist.

Somit gilt:

(98 ⋅ 27) mod 6 ≡ (2 ⋅ 3) mod 6 ≡ 6 mod 6 ≡ 0 mod 6.

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

2: 313²=313¹⁺¹=313¹⋅313¹ ≡ 313⋅313=97969 ≡ 424 mod 929

4: 313⁴=313²⁺²=313²⋅313² ≡ 424⋅424=179776 ≡ 479 mod 929

8: 313⁸=313⁴⁺⁴=313⁴⋅313⁴ ≡ 479⋅479=229441 ≡ 907 mod 929

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

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

127 = 64+32+16+8+4+2+1

507¹²⁷

= 507^{64+32+16+8+4+2+1}

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

≡ 72 ⋅ 325 ⋅ 150 ⋅ 703 ⋅ 829 ⋅ 706 ⋅ 507 mod 887
≡ 23400 ⋅ 150 ⋅ 703 ⋅ 829 ⋅ 706 ⋅ 507 mod 887 ≡ 338 ⋅ 150 ⋅ 703 ⋅ 829 ⋅ 706 ⋅ 507 mod 887
≡ 50700 ⋅ 703 ⋅ 829 ⋅ 706 ⋅ 507 mod 887 ≡ 141 ⋅ 703 ⋅ 829 ⋅ 706 ⋅ 507 mod 887
≡ 99123 ⋅ 829 ⋅ 706 ⋅ 507 mod 887 ≡ 666 ⋅ 829 ⋅ 706 ⋅ 507 mod 887
≡ 552114 ⋅ 706 ⋅ 507 mod 887 ≡ 400 ⋅ 706 ⋅ 507 mod 887
≡ 282400 ⋅ 507 mod 887 ≡ 334 ⋅ 507 mod 887
≡ 169338 mod 887 ≡ 808 mod 887

Es gilt also: 507¹²⁷ ≡ 808 mod 887

Berechnung des größten gemeinsamen Teilers von 59 und 39

=>59	= 1⋅39 + 20
=>39	= 1⋅20 + 19
=>20	= 1⋅19 + 1
=>19	= 19⋅1 + 0

also gilt: ggt(59,39)=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= 20-1⋅19
19= 39-1⋅20	eingesetzt in die Zeile drüber:	1	= 1⋅20 -1⋅(39 -1⋅ 20) = 1⋅20 -1⋅39 +1⋅ 20) = -1⋅39 +2⋅ 20 (=1)
20= 59-1⋅39	eingesetzt in die Zeile drüber:	1	= -1⋅39 +2⋅(59 -1⋅ 39) = -1⋅39 +2⋅59 -2⋅ 39) = 2⋅59 -3⋅ 39 (=1)

Es gilt also: ggt(59,39)=1 = 2⋅59 -3⋅39

oder wenn man 2⋅59 auf die linke Seite bringt:

1 -2⋅59 = -3⋅39

-3⋅39 = -2⋅59 + 1 |+59⋅39

-3⋅39 + 59⋅39 = -2⋅59 + 59⋅39 + 1

(-3 + 59) ⋅ 39 = (-2 + 39) ⋅ 59 + 1

56⋅39 = 37⋅59 + 1

Es gilt also: 56⋅39 = 37⋅59 +1

Somit 56⋅39 = 1 mod 59

56 ist also das Inverse von 39 mod 59