Um längere Rechnungen zu vermeiden, rechnen wir:

(296 - 11996) mod 6 ≡ (296 mod 6 - 11996 mod 6) mod 6.

296 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 296 = 300-4 = 6 ⋅ 50 -4 = 6 ⋅ 50 - 6 + 2.

11996 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 11996 = 12000-4 = 6 ⋅ 2000 -4 = 6 ⋅ 2000 - 6 + 2.

Somit gilt:

(296 - 11996) mod 6 ≡ (2 - 2) mod 6 ≡ 0 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(46 ⋅ 19) mod 3 ≡ (46 mod 3 ⋅ 19 mod 3) mod 3.

46 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 46 = 45 + 1 = 15 ⋅ 3 + 1 ist.

19 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 19 = 18 + 1 = 6 ⋅ 3 + 1 ist.

Somit gilt:

(46 ⋅ 19) mod 3 ≡ (1 ⋅ 1) mod 3 ≡ 1 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: 370¹=370

2: 370²=370¹⁺¹=370¹⋅370¹ ≡ 370⋅370=136900 ≡ 404 mod 449

4: 370⁴=370²⁺²=370²⋅370² ≡ 404⋅404=163216 ≡ 229 mod 449

8: 370⁸=370⁴⁺⁴=370⁴⋅370⁴ ≡ 229⋅229=52441 ≡ 357 mod 449

16: 370¹⁶=370⁸⁺⁸=370⁸⋅370⁸ ≡ 357⋅357=127449 ≡ 382 mod 449

32: 370³²=370¹⁶⁺¹⁶=370¹⁶⋅370¹⁶ ≡ 382⋅382=145924 ≡ 448 mod 449

64: 370⁶⁴=370³²⁺³²=370³²⋅370³² ≡ 448⋅448=200704 ≡ 1 mod 449

128: 370¹²⁸=370⁶⁴⁺⁶⁴=370⁶⁴⋅370⁶⁴ ≡ 1⋅1=1 ≡ 1 mod 449

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

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

191 = 128+32+16+8+4+2+1

776¹⁹¹

= 776^{128+32+16+8+4+2+1}

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

≡ 809 ⋅ 55 ⋅ 350 ⋅ 353 ⋅ 649 ⋅ 835 ⋅ 776 mod 907
≡ 44495 ⋅ 350 ⋅ 353 ⋅ 649 ⋅ 835 ⋅ 776 mod 907 ≡ 52 ⋅ 350 ⋅ 353 ⋅ 649 ⋅ 835 ⋅ 776 mod 907
≡ 18200 ⋅ 353 ⋅ 649 ⋅ 835 ⋅ 776 mod 907 ≡ 60 ⋅ 353 ⋅ 649 ⋅ 835 ⋅ 776 mod 907
≡ 21180 ⋅ 649 ⋅ 835 ⋅ 776 mod 907 ≡ 319 ⋅ 649 ⋅ 835 ⋅ 776 mod 907
≡ 207031 ⋅ 835 ⋅ 776 mod 907 ≡ 235 ⋅ 835 ⋅ 776 mod 907
≡ 196225 ⋅ 776 mod 907 ≡ 313 ⋅ 776 mod 907
≡ 242888 mod 907 ≡ 719 mod 907

Es gilt also: 776¹⁹¹ ≡ 719 mod 907

Berechnung des größten gemeinsamen Teilers von 83 und 33

=>83	= 2⋅33 + 17
=>33	= 1⋅17 + 16
=>17	= 1⋅16 + 1
=>16	= 16⋅1 + 0

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

Es gilt also: ggt(83,33)=1 = 2⋅83 -5⋅33

oder wenn man 2⋅83 auf die linke Seite bringt:

1 -2⋅83 = -5⋅33

-5⋅33 = -2⋅83 + 1 |+83⋅33

-5⋅33 + 83⋅33 = -2⋅83 + 83⋅33 + 1

(-5 + 83) ⋅ 33 = (-2 + 33) ⋅ 83 + 1

78⋅33 = 31⋅83 + 1

Es gilt also: 78⋅33 = 31⋅83 +1

Somit 78⋅33 = 1 mod 83

78 ist also das Inverse von 33 mod 83