Um längere Rechnungen zu vermeiden, rechnen wir:

(27998 - 74) mod 7 ≡ (27998 mod 7 - 74 mod 7) mod 7.

27998 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 27998 = 28000-2 = 7 ⋅ 4000 -2 = 7 ⋅ 4000 - 7 + 5.

74 mod 7 ≡ 4 mod 7 kann man relativ leicht bestimmen, weil ja 74 = 70+4 = 7 ⋅ 10 +4.

Somit gilt:

(27998 - 74) mod 7 ≡ (5 - 4) mod 7 ≡ 1 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(69 ⋅ 58) mod 11 ≡ (69 mod 11 ⋅ 58 mod 11) mod 11.

69 mod 11 ≡ 3 mod 11 kann man relativ leicht bestimmen, weil ja 69 = 66 + 3 = 6 ⋅ 11 + 3 ist.

58 mod 11 ≡ 3 mod 11 kann man relativ leicht bestimmen, weil ja 58 = 55 + 3 = 5 ⋅ 11 + 3 ist.

Somit gilt:

(69 ⋅ 58) mod 11 ≡ (3 ⋅ 3) mod 11 ≡ 9 mod 11.

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

2: 653²=653¹⁺¹=653¹⋅653¹ ≡ 653⋅653=426409 ≡ 136 mod 941

4: 653⁴=653²⁺²=653²⋅653² ≡ 136⋅136=18496 ≡ 617 mod 941

8: 653⁸=653⁴⁺⁴=653⁴⋅653⁴ ≡ 617⋅617=380689 ≡ 525 mod 941

16: 653¹⁶=653⁸⁺⁸=653⁸⋅653⁸ ≡ 525⋅525=275625 ≡ 853 mod 941

32: 653³²=653¹⁶⁺¹⁶=653¹⁶⋅653¹⁶ ≡ 853⋅853=727609 ≡ 216 mod 941

64: 653⁶⁴=653³²⁺³²=653³²⋅653³² ≡ 216⋅216=46656 ≡ 547 mod 941

128: 653¹²⁸=653⁶⁴⁺⁶⁴=653⁶⁴⋅653⁶⁴ ≡ 547⋅547=299209 ≡ 912 mod 941

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

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

177 = 128+32+16+1

173¹⁷⁷

= 173^128+32+16+1

= 173¹²⁸⋅173³²⋅173¹⁶⋅173¹

≡ 359 ⋅ 431 ⋅ 193 ⋅ 173 mod 449
≡ 154729 ⋅ 193 ⋅ 173 mod 449 ≡ 273 ⋅ 193 ⋅ 173 mod 449
≡ 52689 ⋅ 173 mod 449 ≡ 156 ⋅ 173 mod 449
≡ 26988 mod 449 ≡ 48 mod 449

Es gilt also: 173¹⁷⁷ ≡ 48 mod 449

Berechnung des größten gemeinsamen Teilers von 53 und 43

=>53	= 1⋅43 + 10
=>43	= 4⋅10 + 3
=>10	= 3⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(53,43)=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= 10-3⋅3
3= 43-4⋅10	eingesetzt in die Zeile drüber:	1	= 1⋅10 -3⋅(43 -4⋅ 10) = 1⋅10 -3⋅43 +12⋅ 10) = -3⋅43 +13⋅ 10 (=1)
10= 53-1⋅43	eingesetzt in die Zeile drüber:	1	= -3⋅43 +13⋅(53 -1⋅ 43) = -3⋅43 +13⋅53 -13⋅ 43) = 13⋅53 -16⋅ 43 (=1)

Es gilt also: ggt(53,43)=1 = 13⋅53 -16⋅43

oder wenn man 13⋅53 auf die linke Seite bringt:

1 -13⋅53 = -16⋅43

-16⋅43 = -13⋅53 + 1 |+53⋅43

-16⋅43 + 53⋅43 = -13⋅53 + 53⋅43 + 1

(-16 + 53) ⋅ 43 = (-13 + 43) ⋅ 53 + 1

37⋅43 = 30⋅53 + 1

Es gilt also: 37⋅43 = 30⋅53 +1

Somit 37⋅43 = 1 mod 53

37 ist also das Inverse von 43 mod 53