Um längere Rechnungen zu vermeiden, rechnen wir:

(2800 + 2099) mod 7 ≡ (2800 mod 7 + 2099 mod 7) mod 7.

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

2099 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 2099 = 2100-1 = 7 ⋅ 300 -1 = 7 ⋅ 300 - 7 + 6.

Somit gilt:

(2800 + 2099) mod 7 ≡ (0 + 6) mod 7 ≡ 6 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(44 ⋅ 88) mod 10 ≡ (44 mod 10 ⋅ 88 mod 10) mod 10.

44 mod 10 ≡ 4 mod 10 kann man relativ leicht bestimmen, weil ja 44 = 40 + 4 = 4 ⋅ 10 + 4 ist.

88 mod 10 ≡ 8 mod 10 kann man relativ leicht bestimmen, weil ja 88 = 80 + 8 = 8 ⋅ 10 + 8 ist.

Somit gilt:

(44 ⋅ 88) mod 10 ≡ (4 ⋅ 8) mod 10 ≡ 32 mod 10 ≡ 2 mod 10.

Die 16 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: 182¹=182

2: 182²=182¹⁺¹=182¹⋅182¹ ≡ 182⋅182=33124 ≡ 96 mod 359

4: 182⁴=182²⁺²=182²⋅182² ≡ 96⋅96=9216 ≡ 241 mod 359

8: 182⁸=182⁴⁺⁴=182⁴⋅182⁴ ≡ 241⋅241=58081 ≡ 282 mod 359

16: 182¹⁶=182⁸⁺⁸=182⁸⋅182⁸ ≡ 282⋅282=79524 ≡ 185 mod 359

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

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

179 = 128+32+16+2+1

351¹⁷⁹

= 351^{128+32+16+2+1}

= 351¹²⁸⋅351³²⋅351¹⁶⋅351²⋅351¹

≡ 376 ⋅ 505 ⋅ 168 ⋅ 296 ⋅ 351 mod 523
≡ 189880 ⋅ 168 ⋅ 296 ⋅ 351 mod 523 ≡ 31 ⋅ 168 ⋅ 296 ⋅ 351 mod 523
≡ 5208 ⋅ 296 ⋅ 351 mod 523 ≡ 501 ⋅ 296 ⋅ 351 mod 523
≡ 148296 ⋅ 351 mod 523 ≡ 287 ⋅ 351 mod 523
≡ 100737 mod 523 ≡ 321 mod 523

Es gilt also: 351¹⁷⁹ ≡ 321 mod 523

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

=>83	= 1⋅45 + 38
=>45	= 1⋅38 + 7
=>38	= 5⋅7 + 3
=>7	= 2⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(83,45)=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-2⋅3
3= 38-5⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -2⋅(38 -5⋅ 7) = 1⋅7 -2⋅38 +10⋅ 7) = -2⋅38 +11⋅ 7 (=1)
7= 45-1⋅38	eingesetzt in die Zeile drüber:	1	= -2⋅38 +11⋅(45 -1⋅ 38) = -2⋅38 +11⋅45 -11⋅ 38) = 11⋅45 -13⋅ 38 (=1)
38= 83-1⋅45	eingesetzt in die Zeile drüber:	1	= 11⋅45 -13⋅(83 -1⋅ 45) = 11⋅45 -13⋅83 +13⋅ 45) = -13⋅83 +24⋅ 45 (=1)

Es gilt also: ggt(83,45)=1 = -13⋅83 +24⋅45

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

1 +13⋅83 = +24⋅45

Es gilt also: 24⋅45 = 13⋅83 +1

Somit 24⋅45 = 1 mod 83

24 ist also das Inverse von 45 mod 83