Um längere Rechnungen zu vermeiden, rechnen wir:

(2001 + 497) mod 5 ≡ (2001 mod 5 + 497 mod 5) mod 5.

2001 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 2001 = 2000+1 = 5 ⋅ 400 +1.

497 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 497 = 400+97 = 5 ⋅ 80 +97.

Somit gilt:

(2001 + 497) mod 5 ≡ (1 + 2) mod 5 ≡ 3 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(30 ⋅ 54) mod 11 ≡ (30 mod 11 ⋅ 54 mod 11) mod 11.

30 mod 11 ≡ 8 mod 11 kann man relativ leicht bestimmen, weil ja 30 = 22 + 8 = 2 ⋅ 11 + 8 ist.

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

Somit gilt:

(30 ⋅ 54) mod 11 ≡ (8 ⋅ 10) mod 11 ≡ 80 mod 11 ≡ 3 mod 11.

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

2: 419²=419¹⁺¹=419¹⋅419¹ ≡ 419⋅419=175561 ≡ 325 mod 859

4: 419⁴=419²⁺²=419²⋅419² ≡ 325⋅325=105625 ≡ 827 mod 859

8: 419⁸=419⁴⁺⁴=419⁴⋅419⁴ ≡ 827⋅827=683929 ≡ 165 mod 859

16: 419¹⁶=419⁸⁺⁸=419⁸⋅419⁸ ≡ 165⋅165=27225 ≡ 596 mod 859

32: 419³²=419¹⁶⁺¹⁶=419¹⁶⋅419¹⁶ ≡ 596⋅596=355216 ≡ 449 mod 859

64: 419⁶⁴=419³²⁺³²=419³²⋅419³² ≡ 449⋅449=201601 ≡ 595 mod 859

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

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

251 = 128+64+32+16+8+2+1

549²⁵¹

= 549^{128+64+32+16+8+2+1}

= 549¹²⁸⋅549⁶⁴⋅549³²⋅549¹⁶⋅549⁸⋅549²⋅549¹

≡ 141 ⋅ 851 ⋅ 715 ⋅ 825 ⋅ 595 ⋅ 298 ⋅ 549 mod 883
≡ 119991 ⋅ 715 ⋅ 825 ⋅ 595 ⋅ 298 ⋅ 549 mod 883 ≡ 786 ⋅ 715 ⋅ 825 ⋅ 595 ⋅ 298 ⋅ 549 mod 883
≡ 561990 ⋅ 825 ⋅ 595 ⋅ 298 ⋅ 549 mod 883 ≡ 402 ⋅ 825 ⋅ 595 ⋅ 298 ⋅ 549 mod 883
≡ 331650 ⋅ 595 ⋅ 298 ⋅ 549 mod 883 ≡ 525 ⋅ 595 ⋅ 298 ⋅ 549 mod 883
≡ 312375 ⋅ 298 ⋅ 549 mod 883 ≡ 676 ⋅ 298 ⋅ 549 mod 883
≡ 201448 ⋅ 549 mod 883 ≡ 124 ⋅ 549 mod 883
≡ 68076 mod 883 ≡ 85 mod 883

Es gilt also: 549²⁵¹ ≡ 85 mod 883

Berechnung des größten gemeinsamen Teilers von 71 und 55

=>71	= 1⋅55 + 16
=>55	= 3⋅16 + 7
=>16	= 2⋅7 + 2
=>7	= 3⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(71,55)=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= 16-2⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -3⋅(16 -2⋅ 7) = 1⋅7 -3⋅16 +6⋅ 7) = -3⋅16 +7⋅ 7 (=1)
7= 55-3⋅16	eingesetzt in die Zeile drüber:	1	= -3⋅16 +7⋅(55 -3⋅ 16) = -3⋅16 +7⋅55 -21⋅ 16) = 7⋅55 -24⋅ 16 (=1)
16= 71-1⋅55	eingesetzt in die Zeile drüber:	1	= 7⋅55 -24⋅(71 -1⋅ 55) = 7⋅55 -24⋅71 +24⋅ 55) = -24⋅71 +31⋅ 55 (=1)

Es gilt also: ggt(71,55)=1 = -24⋅71 +31⋅55

oder wenn man -24⋅71 auf die linke Seite bringt:

1 +24⋅71 = +31⋅55

Es gilt also: 31⋅55 = 24⋅71 +1

Somit 31⋅55 = 1 mod 71

31 ist also das Inverse von 55 mod 71