Um längere Rechnungen zu vermeiden, rechnen wir:

(2098 + 27993) mod 7 ≡ (2098 mod 7 + 27993 mod 7) mod 7.

2098 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 2098 = 2100-2 = 7 ⋅ 300 -2 = 7 ⋅ 300 - 7 + 5.

27993 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 27993 = 28000-7 = 7 ⋅ 4000 -7 = 7 ⋅ 4000 - 7 + 0.

Somit gilt:

(2098 + 27993) mod 7 ≡ (5 + 0) mod 7 ≡ 5 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(54 ⋅ 60) mod 5 ≡ (54 mod 5 ⋅ 60 mod 5) mod 5.

54 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 54 = 50 + 4 = 10 ⋅ 5 + 4 ist.

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

Somit gilt:

(54 ⋅ 60) mod 5 ≡ (4 ⋅ 0) 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: 367¹=367

2: 367²=367¹⁺¹=367¹⋅367¹ ≡ 367⋅367=134689 ≡ 89 mod 673

4: 367⁴=367²⁺²=367²⋅367² ≡ 89⋅89=7921 ≡ 518 mod 673

8: 367⁸=367⁴⁺⁴=367⁴⋅367⁴ ≡ 518⋅518=268324 ≡ 470 mod 673

16: 367¹⁶=367⁸⁺⁸=367⁸⋅367⁸ ≡ 470⋅470=220900 ≡ 156 mod 673

32: 367³²=367¹⁶⁺¹⁶=367¹⁶⋅367¹⁶ ≡ 156⋅156=24336 ≡ 108 mod 673

64: 367⁶⁴=367³²⁺³²=367³²⋅367³² ≡ 108⋅108=11664 ≡ 223 mod 673

128: 367¹²⁸=367⁶⁴⁺⁶⁴=367⁶⁴⋅367⁶⁴ ≡ 223⋅223=49729 ≡ 600 mod 673

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

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

86 = 64+16+4+2

491⁸⁶

= 491^64+16+4+2

= 491⁶⁴⋅491¹⁶⋅491⁴⋅491²

≡ 119 ⋅ 186 ⋅ 692 ⋅ 349 mod 743
≡ 22134 ⋅ 692 ⋅ 349 mod 743 ≡ 587 ⋅ 692 ⋅ 349 mod 743
≡ 406204 ⋅ 349 mod 743 ≡ 526 ⋅ 349 mod 743
≡ 183574 mod 743 ≡ 53 mod 743

Es gilt also: 491⁸⁶ ≡ 53 mod 743

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

=>83	= 1⋅43 + 40
=>43	= 1⋅40 + 3
=>40	= 13⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(83,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= 40-13⋅3
3= 43-1⋅40	eingesetzt in die Zeile drüber:	1	= 1⋅40 -13⋅(43 -1⋅ 40) = 1⋅40 -13⋅43 +13⋅ 40) = -13⋅43 +14⋅ 40 (=1)
40= 83-1⋅43	eingesetzt in die Zeile drüber:	1	= -13⋅43 +14⋅(83 -1⋅ 43) = -13⋅43 +14⋅83 -14⋅ 43) = 14⋅83 -27⋅ 43 (=1)

Es gilt also: ggt(83,43)=1 = 14⋅83 -27⋅43

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

1 -14⋅83 = -27⋅43

-27⋅43 = -14⋅83 + 1 |+83⋅43

-27⋅43 + 83⋅43 = -14⋅83 + 83⋅43 + 1

(-27 + 83) ⋅ 43 = (-14 + 43) ⋅ 83 + 1

56⋅43 = 29⋅83 + 1

Es gilt also: 56⋅43 = 29⋅83 +1

Somit 56⋅43 = 1 mod 83

56 ist also das Inverse von 43 mod 83