Um längere Rechnungen zu vermeiden, rechnen wir:

(12000 + 1999) mod 4 ≡ (12000 mod 4 + 1999 mod 4) mod 4.

12000 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 12000 = 12000+0 = 4 ⋅ 3000 +0.

1999 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 1999 = 1900+99 = 4 ⋅ 475 +99.

Somit gilt:

(12000 + 1999) mod 4 ≡ (0 + 3) mod 4 ≡ 3 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(43 ⋅ 34) mod 10 ≡ (43 mod 10 ⋅ 34 mod 10) mod 10.

43 mod 10 ≡ 3 mod 10 kann man relativ leicht bestimmen, weil ja 43 = 40 + 3 = 4 ⋅ 10 + 3 ist.

34 mod 10 ≡ 4 mod 10 kann man relativ leicht bestimmen, weil ja 34 = 30 + 4 = 3 ⋅ 10 + 4 ist.

Somit gilt:

(43 ⋅ 34) mod 10 ≡ (3 ⋅ 4) mod 10 ≡ 12 mod 10 ≡ 2 mod 10.

Die 32 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: 829¹=829

2: 829²=829¹⁺¹=829¹⋅829¹ ≡ 829⋅829=687241 ≡ 671 mod 967

4: 829⁴=829²⁺²=829²⋅829² ≡ 671⋅671=450241 ≡ 586 mod 967

8: 829⁸=829⁴⁺⁴=829⁴⋅829⁴ ≡ 586⋅586=343396 ≡ 111 mod 967

16: 829¹⁶=829⁸⁺⁸=829⁸⋅829⁸ ≡ 111⋅111=12321 ≡ 717 mod 967

32: 829³²=829¹⁶⁺¹⁶=829¹⁶⋅829¹⁶ ≡ 717⋅717=514089 ≡ 612 mod 967

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

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

127 = 64+32+16+8+4+2+1

486¹²⁷

= 486^{64+32+16+8+4+2+1}

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

≡ 421 ⋅ 54 ⋅ 308 ⋅ 451 ⋅ 118 ⋅ 169 ⋅ 486 mod 499
≡ 22734 ⋅ 308 ⋅ 451 ⋅ 118 ⋅ 169 ⋅ 486 mod 499 ≡ 279 ⋅ 308 ⋅ 451 ⋅ 118 ⋅ 169 ⋅ 486 mod 499
≡ 85932 ⋅ 451 ⋅ 118 ⋅ 169 ⋅ 486 mod 499 ≡ 104 ⋅ 451 ⋅ 118 ⋅ 169 ⋅ 486 mod 499
≡ 46904 ⋅ 118 ⋅ 169 ⋅ 486 mod 499 ≡ 497 ⋅ 118 ⋅ 169 ⋅ 486 mod 499
≡ 58646 ⋅ 169 ⋅ 486 mod 499 ≡ 263 ⋅ 169 ⋅ 486 mod 499
≡ 44447 ⋅ 486 mod 499 ≡ 36 ⋅ 486 mod 499
≡ 17496 mod 499 ≡ 31 mod 499

Es gilt also: 486¹²⁷ ≡ 31 mod 499

Berechnung des größten gemeinsamen Teilers von 89 und 72

=>89	= 1⋅72 + 17
=>72	= 4⋅17 + 4
=>17	= 4⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(89,72)=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= 17-4⋅4
4= 72-4⋅17	eingesetzt in die Zeile drüber:	1	= 1⋅17 -4⋅(72 -4⋅ 17) = 1⋅17 -4⋅72 +16⋅ 17) = -4⋅72 +17⋅ 17 (=1)
17= 89-1⋅72	eingesetzt in die Zeile drüber:	1	= -4⋅72 +17⋅(89 -1⋅ 72) = -4⋅72 +17⋅89 -17⋅ 72) = 17⋅89 -21⋅ 72 (=1)

Es gilt also: ggt(89,72)=1 = 17⋅89 -21⋅72

oder wenn man 17⋅89 auf die linke Seite bringt:

1 -17⋅89 = -21⋅72

-21⋅72 = -17⋅89 + 1 |+89⋅72

-21⋅72 + 89⋅72 = -17⋅89 + 89⋅72 + 1

(-21 + 89) ⋅ 72 = (-17 + 72) ⋅ 89 + 1

68⋅72 = 55⋅89 + 1

Es gilt also: 68⋅72 = 55⋅89 +1

Somit 68⋅72 = 1 mod 89

68 ist also das Inverse von 72 mod 89