Um längere Rechnungen zu vermeiden, rechnen wir:

(280 - 2802) mod 7 ≡ (280 mod 7 - 2802 mod 7) mod 7.

280 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 280 = 280+0 = 7 ⋅ 40 +0.

2802 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 2802 = 2800+2 = 7 ⋅ 400 +2.

Somit gilt:

(280 - 2802) mod 7 ≡ (0 - 2) mod 7 ≡ -2 mod 7 ≡ 5 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(81 ⋅ 39) mod 3 ≡ (81 mod 3 ⋅ 39 mod 3) mod 3.

81 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 81 = 81 + 0 = 27 ⋅ 3 + 0 ist.

39 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 39 = 39 + 0 = 13 ⋅ 3 + 0 ist.

Somit gilt:

(81 ⋅ 39) mod 3 ≡ (0 ⋅ 0) mod 3 ≡ 0 mod 3.

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

2: 388²=388¹⁺¹=388¹⋅388¹ ≡ 388⋅388=150544 ≡ 497 mod 661

4: 388⁴=388²⁺²=388²⋅388² ≡ 497⋅497=247009 ≡ 456 mod 661

8: 388⁸=388⁴⁺⁴=388⁴⋅388⁴ ≡ 456⋅456=207936 ≡ 382 mod 661

16: 388¹⁶=388⁸⁺⁸=388⁸⋅388⁸ ≡ 382⋅382=145924 ≡ 504 mod 661

32: 388³²=388¹⁶⁺¹⁶=388¹⁶⋅388¹⁶ ≡ 504⋅504=254016 ≡ 192 mod 661

64: 388⁶⁴=388³²⁺³²=388³²⋅388³² ≡ 192⋅192=36864 ≡ 509 mod 661

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

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

165 = 128+32+4+1

235¹⁶⁵

= 235^128+32+4+1

= 235¹²⁸⋅235³²⋅235⁴⋅235¹

≡ 297 ⋅ 246 ⋅ 3 ⋅ 235 mod 421
≡ 73062 ⋅ 3 ⋅ 235 mod 421 ≡ 229 ⋅ 3 ⋅ 235 mod 421
≡ 687 ⋅ 235 mod 421 ≡ 266 ⋅ 235 mod 421
≡ 62510 mod 421 ≡ 202 mod 421

Es gilt also: 235¹⁶⁵ ≡ 202 mod 421

Berechnung des größten gemeinsamen Teilers von 83 und 76

=>83	= 1⋅76 + 7
=>76	= 10⋅7 + 6
=>7	= 1⋅6 + 1
=>6	= 6⋅1 + 0

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

Es gilt also: ggt(83,76)=1 = 11⋅83 -12⋅76

oder wenn man 11⋅83 auf die linke Seite bringt:

1 -11⋅83 = -12⋅76

-12⋅76 = -11⋅83 + 1 |+83⋅76

-12⋅76 + 83⋅76 = -11⋅83 + 83⋅76 + 1

(-12 + 83) ⋅ 76 = (-11 + 76) ⋅ 83 + 1

71⋅76 = 65⋅83 + 1

Es gilt also: 71⋅76 = 65⋅83 +1

Somit 71⋅76 = 1 mod 83

71 ist also das Inverse von 76 mod 83