Um längere Rechnungen zu vermeiden, rechnen wir:

(34996 - 20996) mod 7 ≡ (34996 mod 7 - 20996 mod 7) mod 7.

34996 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 34996 = 35000-4 = 7 ⋅ 5000 -4 = 7 ⋅ 5000 - 7 + 3.

20996 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 20996 = 21000-4 = 7 ⋅ 3000 -4 = 7 ⋅ 3000 - 7 + 3.

Somit gilt:

(34996 - 20996) mod 7 ≡ (3 - 3) mod 7 ≡ 0 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(31 ⋅ 49) mod 9 ≡ (31 mod 9 ⋅ 49 mod 9) mod 9.

31 mod 9 ≡ 4 mod 9 kann man relativ leicht bestimmen, weil ja 31 = 27 + 4 = 3 ⋅ 9 + 4 ist.

49 mod 9 ≡ 4 mod 9 kann man relativ leicht bestimmen, weil ja 49 = 45 + 4 = 5 ⋅ 9 + 4 ist.

Somit gilt:

(31 ⋅ 49) mod 9 ≡ (4 ⋅ 4) mod 9 ≡ 16 mod 9 ≡ 7 mod 9.

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

2: 209²=209¹⁺¹=209¹⋅209¹ ≡ 209⋅209=43681 ≡ 423 mod 503

4: 209⁴=209²⁺²=209²⋅209² ≡ 423⋅423=178929 ≡ 364 mod 503

8: 209⁸=209⁴⁺⁴=209⁴⋅209⁴ ≡ 364⋅364=132496 ≡ 207 mod 503

16: 209¹⁶=209⁸⁺⁸=209⁸⋅209⁸ ≡ 207⋅207=42849 ≡ 94 mod 503

32: 209³²=209¹⁶⁺¹⁶=209¹⁶⋅209¹⁶ ≡ 94⋅94=8836 ≡ 285 mod 503

64: 209⁶⁴=209³²⁺³²=209³²⋅209³² ≡ 285⋅285=81225 ≡ 242 mod 503

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

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

90 = 64+16+8+2

290⁹⁰

= 290^64+16+8+2

= 290⁶⁴⋅290¹⁶⋅290⁸⋅290²

≡ 550 ⋅ 464 ⋅ 534 ⋅ 489 mod 691
≡ 255200 ⋅ 534 ⋅ 489 mod 691 ≡ 221 ⋅ 534 ⋅ 489 mod 691
≡ 118014 ⋅ 489 mod 691 ≡ 544 ⋅ 489 mod 691
≡ 266016 mod 691 ≡ 672 mod 691

Es gilt also: 290⁹⁰ ≡ 672 mod 691

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

=>53	= 1⋅30 + 23
=>30	= 1⋅23 + 7
=>23	= 3⋅7 + 2
=>7	= 3⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(53,30)=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-3⋅2
2= 23-3⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -3⋅(23 -3⋅ 7) = 1⋅7 -3⋅23 +9⋅ 7) = -3⋅23 +10⋅ 7 (=1)
7= 30-1⋅23	eingesetzt in die Zeile drüber:	1	= -3⋅23 +10⋅(30 -1⋅ 23) = -3⋅23 +10⋅30 -10⋅ 23) = 10⋅30 -13⋅ 23 (=1)
23= 53-1⋅30	eingesetzt in die Zeile drüber:	1	= 10⋅30 -13⋅(53 -1⋅ 30) = 10⋅30 -13⋅53 +13⋅ 30) = -13⋅53 +23⋅ 30 (=1)

Es gilt also: ggt(53,30)=1 = -13⋅53 +23⋅30

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

1 +13⋅53 = +23⋅30

Es gilt also: 23⋅30 = 13⋅53 +1

Somit 23⋅30 = 1 mod 53

23 ist also das Inverse von 30 mod 53