Um längere Rechnungen zu vermeiden, rechnen wir:

(2700 - 4498) mod 9 ≡ (2700 mod 9 - 4498 mod 9) mod 9.

2700 mod 9 ≡ 0 mod 9 kann man relativ leicht bestimmen, weil ja 2700 = 2700+0 = 9 ⋅ 300 +0.

4498 mod 9 ≡ 7 mod 9 kann man relativ leicht bestimmen, weil ja 4498 = 4500-2 = 9 ⋅ 500 -2 = 9 ⋅ 500 - 9 + 7.

Somit gilt:

(2700 - 4498) mod 9 ≡ (0 - 7) mod 9 ≡ -7 mod 9 ≡ 2 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(81 ⋅ 42) mod 6 ≡ (81 mod 6 ⋅ 42 mod 6) mod 6.

81 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 81 = 78 + 3 = 13 ⋅ 6 + 3 ist.

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

Somit gilt:

(81 ⋅ 42) mod 6 ≡ (3 ⋅ 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: 337¹=337

2: 337²=337¹⁺¹=337¹⋅337¹ ≡ 337⋅337=113569 ≡ 27 mod 397

4: 337⁴=337²⁺²=337²⋅337² ≡ 27⋅27=729 ≡ 332 mod 397

8: 337⁸=337⁴⁺⁴=337⁴⋅337⁴ ≡ 332⋅332=110224 ≡ 255 mod 397

16: 337¹⁶=337⁸⁺⁸=337⁸⋅337⁸ ≡ 255⋅255=65025 ≡ 314 mod 397

32: 337³²=337¹⁶⁺¹⁶=337¹⁶⋅337¹⁶ ≡ 314⋅314=98596 ≡ 140 mod 397

64: 337⁶⁴=337³²⁺³²=337³²⋅337³² ≡ 140⋅140=19600 ≡ 147 mod 397

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

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

85 = 64+16+4+1

404⁸⁵

= 404^64+16+4+1

= 404⁶⁴⋅404¹⁶⋅404⁴⋅404¹

≡ 475 ⋅ 145 ⋅ 561 ⋅ 404 mod 757
≡ 68875 ⋅ 561 ⋅ 404 mod 757 ≡ 745 ⋅ 561 ⋅ 404 mod 757
≡ 417945 ⋅ 404 mod 757 ≡ 81 ⋅ 404 mod 757
≡ 32724 mod 757 ≡ 173 mod 757

Es gilt also: 404⁸⁵ ≡ 173 mod 757

Berechnung des größten gemeinsamen Teilers von 73 und 38

=>73	= 1⋅38 + 35
=>38	= 1⋅35 + 3
=>35	= 11⋅3 + 2
=>3	= 1⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(73,38)=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= 3-1⋅2
2= 35-11⋅3	eingesetzt in die Zeile drüber:	1	= 1⋅3 -1⋅(35 -11⋅ 3) = 1⋅3 -1⋅35 +11⋅ 3) = -1⋅35 +12⋅ 3 (=1)
3= 38-1⋅35	eingesetzt in die Zeile drüber:	1	= -1⋅35 +12⋅(38 -1⋅ 35) = -1⋅35 +12⋅38 -12⋅ 35) = 12⋅38 -13⋅ 35 (=1)
35= 73-1⋅38	eingesetzt in die Zeile drüber:	1	= 12⋅38 -13⋅(73 -1⋅ 38) = 12⋅38 -13⋅73 +13⋅ 38) = -13⋅73 +25⋅ 38 (=1)

Es gilt also: ggt(73,38)=1 = -13⋅73 +25⋅38

oder wenn man -13⋅73 auf die linke Seite bringt:

1 +13⋅73 = +25⋅38

Es gilt also: 25⋅38 = 13⋅73 +1

Somit 25⋅38 = 1 mod 73

25 ist also das Inverse von 38 mod 73