Um längere Rechnungen zu vermeiden, rechnen wir:

(23996 - 17995) mod 6 ≡ (23996 mod 6 - 17995 mod 6) mod 6.

23996 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 23996 = 24000-4 = 6 ⋅ 4000 -4 = 6 ⋅ 4000 - 6 + 2.

17995 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 17995 = 18000-5 = 6 ⋅ 3000 -5 = 6 ⋅ 3000 - 6 + 1.

Somit gilt:

(23996 - 17995) mod 6 ≡ (2 - 1) mod 6 ≡ 1 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(97 ⋅ 81) mod 10 ≡ (97 mod 10 ⋅ 81 mod 10) mod 10.

97 mod 10 ≡ 7 mod 10 kann man relativ leicht bestimmen, weil ja 97 = 90 + 7 = 9 ⋅ 10 + 7 ist.

81 mod 10 ≡ 1 mod 10 kann man relativ leicht bestimmen, weil ja 81 = 80 + 1 = 8 ⋅ 10 + 1 ist.

Somit gilt:

(97 ⋅ 81) mod 10 ≡ (7 ⋅ 1) mod 10 ≡ 7 mod 10.

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

2: 346²=346¹⁺¹=346¹⋅346¹ ≡ 346⋅346=119716 ≡ 804 mod 929

4: 346⁴=346²⁺²=346²⋅346² ≡ 804⋅804=646416 ≡ 761 mod 929

8: 346⁸=346⁴⁺⁴=346⁴⋅346⁴ ≡ 761⋅761=579121 ≡ 354 mod 929

16: 346¹⁶=346⁸⁺⁸=346⁸⋅346⁸ ≡ 354⋅354=125316 ≡ 830 mod 929

32: 346³²=346¹⁶⁺¹⁶=346¹⁶⋅346¹⁶ ≡ 830⋅830=688900 ≡ 511 mod 929

64: 346⁶⁴=346³²⁺³²=346³²⋅346³² ≡ 511⋅511=261121 ≡ 72 mod 929

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

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

109 = 64+32+8+4+1

654¹⁰⁹

= 654^64+32+8+4+1

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

≡ 223 ⋅ 108 ⋅ 203 ⋅ 432 ⋅ 654 mod 673
≡ 24084 ⋅ 203 ⋅ 432 ⋅ 654 mod 673 ≡ 529 ⋅ 203 ⋅ 432 ⋅ 654 mod 673
≡ 107387 ⋅ 432 ⋅ 654 mod 673 ≡ 380 ⋅ 432 ⋅ 654 mod 673
≡ 164160 ⋅ 654 mod 673 ≡ 621 ⋅ 654 mod 673
≡ 406134 mod 673 ≡ 315 mod 673

Es gilt also: 654¹⁰⁹ ≡ 315 mod 673

Berechnung des größten gemeinsamen Teilers von 101 und 42

=>101	= 2⋅42 + 17
=>42	= 2⋅17 + 8
=>17	= 2⋅8 + 1
=>8	= 8⋅1 + 0

also gilt: ggt(101,42)=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-2⋅8
8= 42-2⋅17	eingesetzt in die Zeile drüber:	1	= 1⋅17 -2⋅(42 -2⋅ 17) = 1⋅17 -2⋅42 +4⋅ 17) = -2⋅42 +5⋅ 17 (=1)
17= 101-2⋅42	eingesetzt in die Zeile drüber:	1	= -2⋅42 +5⋅(101 -2⋅ 42) = -2⋅42 +5⋅101 -10⋅ 42) = 5⋅101 -12⋅ 42 (=1)

Es gilt also: ggt(101,42)=1 = 5⋅101 -12⋅42

oder wenn man 5⋅101 auf die linke Seite bringt:

1 -5⋅101 = -12⋅42

-12⋅42 = -5⋅101 + 1 |+101⋅42

-12⋅42 + 101⋅42 = -5⋅101 + 101⋅42 + 1

(-12 + 101) ⋅ 42 = (-5 + 42) ⋅ 101 + 1

89⋅42 = 37⋅101 + 1

Es gilt also: 89⋅42 = 37⋅101 +1

Somit 89⋅42 = 1 mod 101

89 ist also das Inverse von 42 mod 101