Um längere Rechnungen zu vermeiden, rechnen wir:

(2697 - 1800) mod 9 ≡ (2697 mod 9 - 1800 mod 9) mod 9.

2697 mod 9 ≡ 6 mod 9 kann man relativ leicht bestimmen, weil ja 2697 = 2700-3 = 9 ⋅ 300 -3 = 9 ⋅ 300 - 9 + 6.

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

Somit gilt:

(2697 - 1800) mod 9 ≡ (6 - 0) mod 9 ≡ 6 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

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

50 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 50 = 48 + 2 = 8 ⋅ 6 + 2 ist.

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

Somit gilt:

(50 ⋅ 96) mod 6 ≡ (2 ⋅ 0) mod 6 ≡ 0 mod 6.

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

2: 544²=544¹⁺¹=544¹⋅544¹ ≡ 544⋅544=295936 ≡ 537 mod 733

4: 544⁴=544²⁺²=544²⋅544² ≡ 537⋅537=288369 ≡ 300 mod 733

8: 544⁸=544⁴⁺⁴=544⁴⋅544⁴ ≡ 300⋅300=90000 ≡ 574 mod 733

16: 544¹⁶=544⁸⁺⁸=544⁸⋅544⁸ ≡ 574⋅574=329476 ≡ 359 mod 733

32: 544³²=544¹⁶⁺¹⁶=544¹⁶⋅544¹⁶ ≡ 359⋅359=128881 ≡ 606 mod 733

64: 544⁶⁴=544³²⁺³²=544³²⋅544³² ≡ 606⋅606=367236 ≡ 3 mod 733

128: 544¹²⁸=544⁶⁴⁺⁶⁴=544⁶⁴⋅544⁶⁴ ≡ 3⋅3=9 ≡ 9 mod 733

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

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

157 = 128+16+8+4+1

497¹⁵⁷

= 497^128+16+8+4+1

= 497¹²⁸⋅497¹⁶⋅497⁸⋅497⁴⋅497¹

≡ 140 ⋅ 124 ⋅ 140 ⋅ 48 ⋅ 497 mod 541
≡ 17360 ⋅ 140 ⋅ 48 ⋅ 497 mod 541 ≡ 48 ⋅ 140 ⋅ 48 ⋅ 497 mod 541
≡ 6720 ⋅ 48 ⋅ 497 mod 541 ≡ 228 ⋅ 48 ⋅ 497 mod 541
≡ 10944 ⋅ 497 mod 541 ≡ 124 ⋅ 497 mod 541
≡ 61628 mod 541 ≡ 495 mod 541

Es gilt also: 497¹⁵⁷ ≡ 495 mod 541

Berechnung des größten gemeinsamen Teilers von 67 und 28

=>67	= 2⋅28 + 11
=>28	= 2⋅11 + 6
=>11	= 1⋅6 + 5
=>6	= 1⋅5 + 1
=>5	= 5⋅1 + 0

also gilt: ggt(67,28)=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= 6-1⋅5
5= 11-1⋅6	eingesetzt in die Zeile drüber:	1	= 1⋅6 -1⋅(11 -1⋅ 6) = 1⋅6 -1⋅11 +1⋅ 6) = -1⋅11 +2⋅ 6 (=1)
6= 28-2⋅11	eingesetzt in die Zeile drüber:	1	= -1⋅11 +2⋅(28 -2⋅ 11) = -1⋅11 +2⋅28 -4⋅ 11) = 2⋅28 -5⋅ 11 (=1)
11= 67-2⋅28	eingesetzt in die Zeile drüber:	1	= 2⋅28 -5⋅(67 -2⋅ 28) = 2⋅28 -5⋅67 +10⋅ 28) = -5⋅67 +12⋅ 28 (=1)

Es gilt also: ggt(67,28)=1 = -5⋅67 +12⋅28

oder wenn man -5⋅67 auf die linke Seite bringt:

1 +5⋅67 = +12⋅28

Es gilt also: 12⋅28 = 5⋅67 +1

Somit 12⋅28 = 1 mod 67

12 ist also das Inverse von 28 mod 67