Um längere Rechnungen zu vermeiden, rechnen wir:

(11998 + 15000) mod 3 ≡ (11998 mod 3 + 15000 mod 3) mod 3.

11998 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 11998 = 12000-2 = 3 ⋅ 4000 -2 = 3 ⋅ 4000 - 3 + 1.

15000 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 15000 = 15000+0 = 3 ⋅ 5000 +0.

Somit gilt:

(11998 + 15000) mod 3 ≡ (1 + 0) mod 3 ≡ 1 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(61 ⋅ 59) mod 3 ≡ (61 mod 3 ⋅ 59 mod 3) mod 3.

61 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 61 = 60 + 1 = 20 ⋅ 3 + 1 ist.

59 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 59 = 57 + 2 = 19 ⋅ 3 + 2 ist.

Somit gilt:

(61 ⋅ 59) mod 3 ≡ (1 ⋅ 2) mod 3 ≡ 2 mod 3.

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

2: 285²=285¹⁺¹=285¹⋅285¹ ≡ 285⋅285=81225 ≡ 378 mod 691

4: 285⁴=285²⁺²=285²⋅285² ≡ 378⋅378=142884 ≡ 538 mod 691

8: 285⁸=285⁴⁺⁴=285⁴⋅285⁴ ≡ 538⋅538=289444 ≡ 606 mod 691

16: 285¹⁶=285⁸⁺⁸=285⁸⋅285⁸ ≡ 606⋅606=367236 ≡ 315 mod 691

32: 285³²=285¹⁶⁺¹⁶=285¹⁶⋅285¹⁶ ≡ 315⋅315=99225 ≡ 412 mod 691

64: 285⁶⁴=285³²⁺³²=285³²⋅285³² ≡ 412⋅412=169744 ≡ 449 mod 691

128: 285¹²⁸=285⁶⁴⁺⁶⁴=285⁶⁴⋅285⁶⁴ ≡ 449⋅449=201601 ≡ 520 mod 691

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

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

247 = 128+64+32+16+4+2+1

940²⁴⁷

= 940^{128+64+32+16+4+2+1}

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

≡ 251 ⋅ 234 ⋅ 956 ⋅ 652 ⋅ 635 ⋅ 619 ⋅ 940 mod 991
≡ 58734 ⋅ 956 ⋅ 652 ⋅ 635 ⋅ 619 ⋅ 940 mod 991 ≡ 265 ⋅ 956 ⋅ 652 ⋅ 635 ⋅ 619 ⋅ 940 mod 991
≡ 253340 ⋅ 652 ⋅ 635 ⋅ 619 ⋅ 940 mod 991 ≡ 635 ⋅ 652 ⋅ 635 ⋅ 619 ⋅ 940 mod 991
≡ 414020 ⋅ 635 ⋅ 619 ⋅ 940 mod 991 ≡ 773 ⋅ 635 ⋅ 619 ⋅ 940 mod 991
≡ 490855 ⋅ 619 ⋅ 940 mod 991 ≡ 310 ⋅ 619 ⋅ 940 mod 991
≡ 191890 ⋅ 940 mod 991 ≡ 627 ⋅ 940 mod 991
≡ 589380 mod 991 ≡ 726 mod 991

Es gilt also: 940²⁴⁷ ≡ 726 mod 991

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

=>79	= 1⋅71 + 8
=>71	= 8⋅8 + 7
=>8	= 1⋅7 + 1
=>7	= 7⋅1 + 0

also gilt: ggt(79,71)=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= 8-1⋅7
7= 71-8⋅8	eingesetzt in die Zeile drüber:	1	= 1⋅8 -1⋅(71 -8⋅ 8) = 1⋅8 -1⋅71 +8⋅ 8) = -1⋅71 +9⋅ 8 (=1)
8= 79-1⋅71	eingesetzt in die Zeile drüber:	1	= -1⋅71 +9⋅(79 -1⋅ 71) = -1⋅71 +9⋅79 -9⋅ 71) = 9⋅79 -10⋅ 71 (=1)

Es gilt also: ggt(79,71)=1 = 9⋅79 -10⋅71

oder wenn man 9⋅79 auf die linke Seite bringt:

1 -9⋅79 = -10⋅71

-10⋅71 = -9⋅79 + 1 |+79⋅71

-10⋅71 + 79⋅71 = -9⋅79 + 79⋅71 + 1

(-10 + 79) ⋅ 71 = (-9 + 71) ⋅ 79 + 1

69⋅71 = 62⋅79 + 1

Es gilt also: 69⋅71 = 62⋅79 +1

Somit 69⋅71 = 1 mod 79

69 ist also das Inverse von 71 mod 79