Um längere Rechnungen zu vermeiden, rechnen wir:

(2806 + 7002) mod 7 ≡ (2806 mod 7 + 7002 mod 7) mod 7.

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

7002 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 7002 = 7000+2 = 7 ⋅ 1000 +2.

Somit gilt:

(2806 + 7002) mod 7 ≡ (6 + 2) mod 7 ≡ 8 mod 7 ≡ 1 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(75 ⋅ 76) mod 5 ≡ (75 mod 5 ⋅ 76 mod 5) mod 5.

75 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 75 = 75 + 0 = 15 ⋅ 5 + 0 ist.

76 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 76 = 75 + 1 = 15 ⋅ 5 + 1 ist.

Somit gilt:

(75 ⋅ 76) mod 5 ≡ (0 ⋅ 1) mod 5 ≡ 0 mod 5.

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

2: 134²=134¹⁺¹=134¹⋅134¹ ≡ 134⋅134=17956 ≡ 70 mod 271

4: 134⁴=134²⁺²=134²⋅134² ≡ 70⋅70=4900 ≡ 22 mod 271

8: 134⁸=134⁴⁺⁴=134⁴⋅134⁴ ≡ 22⋅22=484 ≡ 213 mod 271

16: 134¹⁶=134⁸⁺⁸=134⁸⋅134⁸ ≡ 213⋅213=45369 ≡ 112 mod 271

32: 134³²=134¹⁶⁺¹⁶=134¹⁶⋅134¹⁶ ≡ 112⋅112=12544 ≡ 78 mod 271

64: 134⁶⁴=134³²⁺³²=134³²⋅134³² ≡ 78⋅78=6084 ≡ 122 mod 271

128: 134¹²⁸=134⁶⁴⁺⁶⁴=134⁶⁴⋅134⁶⁴ ≡ 122⋅122=14884 ≡ 250 mod 271

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

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

167 = 128+32+4+2+1

248¹⁶⁷

= 248^128+32+4+2+1

= 248¹²⁸⋅248³²⋅248⁴⋅248²⋅248¹

≡ 257 ⋅ 293 ⋅ 518 ⋅ 122 ⋅ 248 mod 653
≡ 75301 ⋅ 518 ⋅ 122 ⋅ 248 mod 653 ≡ 206 ⋅ 518 ⋅ 122 ⋅ 248 mod 653
≡ 106708 ⋅ 122 ⋅ 248 mod 653 ≡ 269 ⋅ 122 ⋅ 248 mod 653
≡ 32818 ⋅ 248 mod 653 ≡ 168 ⋅ 248 mod 653
≡ 41664 mod 653 ≡ 525 mod 653

Es gilt also: 248¹⁶⁷ ≡ 525 mod 653

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

=>73	= 1⋅51 + 22
=>51	= 2⋅22 + 7
=>22	= 3⋅7 + 1
=>7	= 7⋅1 + 0

also gilt: ggt(73,51)=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= 22-3⋅7
7= 51-2⋅22	eingesetzt in die Zeile drüber:	1	= 1⋅22 -3⋅(51 -2⋅ 22) = 1⋅22 -3⋅51 +6⋅ 22) = -3⋅51 +7⋅ 22 (=1)
22= 73-1⋅51	eingesetzt in die Zeile drüber:	1	= -3⋅51 +7⋅(73 -1⋅ 51) = -3⋅51 +7⋅73 -7⋅ 51) = 7⋅73 -10⋅ 51 (=1)

Es gilt also: ggt(73,51)=1 = 7⋅73 -10⋅51

oder wenn man 7⋅73 auf die linke Seite bringt:

1 -7⋅73 = -10⋅51

-10⋅51 = -7⋅73 + 1 |+73⋅51

-10⋅51 + 73⋅51 = -7⋅73 + 73⋅51 + 1

(-10 + 73) ⋅ 51 = (-7 + 51) ⋅ 73 + 1

63⋅51 = 44⋅73 + 1

Es gilt also: 63⋅51 = 44⋅73 +1

Somit 63⋅51 = 1 mod 73

63 ist also das Inverse von 51 mod 73