Um längere Rechnungen zu vermeiden, rechnen wir:

(2998 - 2398) mod 6 ≡ (2998 mod 6 - 2398 mod 6) mod 6.

2998 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 2998 = 3000-2 = 6 ⋅ 500 -2 = 6 ⋅ 500 - 6 + 4.

2398 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 2398 = 2400-2 = 6 ⋅ 400 -2 = 6 ⋅ 400 - 6 + 4.

Somit gilt:

(2998 - 2398) mod 6 ≡ (4 - 4) mod 6 ≡ 0 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(83 ⋅ 47) mod 6 ≡ (83 mod 6 ⋅ 47 mod 6) mod 6.

83 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 83 = 78 + 5 = 13 ⋅ 6 + 5 ist.

47 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 47 = 42 + 5 = 7 ⋅ 6 + 5 ist.

Somit gilt:

(83 ⋅ 47) mod 6 ≡ (5 ⋅ 5) mod 6 ≡ 25 mod 6 ≡ 1 mod 6.

Die 8 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: 293¹=293

2: 293²=293¹⁺¹=293¹⋅293¹ ≡ 293⋅293=85849 ≡ 115 mod 433

4: 293⁴=293²⁺²=293²⋅293² ≡ 115⋅115=13225 ≡ 235 mod 433

8: 293⁸=293⁴⁺⁴=293⁴⋅293⁴ ≡ 235⋅235=55225 ≡ 234 mod 433

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

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

123 = 64+32+16+8+2+1

364¹²³

= 364^{64+32+16+8+2+1}

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

≡ 314 ⋅ 582 ⋅ 37 ⋅ 282 ⋅ 280 ⋅ 364 mod 787
≡ 182748 ⋅ 37 ⋅ 282 ⋅ 280 ⋅ 364 mod 787 ≡ 164 ⋅ 37 ⋅ 282 ⋅ 280 ⋅ 364 mod 787
≡ 6068 ⋅ 282 ⋅ 280 ⋅ 364 mod 787 ≡ 559 ⋅ 282 ⋅ 280 ⋅ 364 mod 787
≡ 157638 ⋅ 280 ⋅ 364 mod 787 ≡ 238 ⋅ 280 ⋅ 364 mod 787
≡ 66640 ⋅ 364 mod 787 ≡ 532 ⋅ 364 mod 787
≡ 193648 mod 787 ≡ 46 mod 787

Es gilt also: 364¹²³ ≡ 46 mod 787

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

=>89	= 1⋅48 + 41
=>48	= 1⋅41 + 7
=>41	= 5⋅7 + 6
=>7	= 1⋅6 + 1
=>6	= 6⋅1 + 0

also gilt: ggt(89,48)=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-1⋅6
6= 41-5⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -1⋅(41 -5⋅ 7) = 1⋅7 -1⋅41 +5⋅ 7) = -1⋅41 +6⋅ 7 (=1)
7= 48-1⋅41	eingesetzt in die Zeile drüber:	1	= -1⋅41 +6⋅(48 -1⋅ 41) = -1⋅41 +6⋅48 -6⋅ 41) = 6⋅48 -7⋅ 41 (=1)
41= 89-1⋅48	eingesetzt in die Zeile drüber:	1	= 6⋅48 -7⋅(89 -1⋅ 48) = 6⋅48 -7⋅89 +7⋅ 48) = -7⋅89 +13⋅ 48 (=1)

Es gilt also: ggt(89,48)=1 = -7⋅89 +13⋅48

oder wenn man -7⋅89 auf die linke Seite bringt:

1 +7⋅89 = +13⋅48

Es gilt also: 13⋅48 = 7⋅89 +1

Somit 13⋅48 = 1 mod 89

13 ist also das Inverse von 48 mod 89