Um längere Rechnungen zu vermeiden, rechnen wir:

(402 - 7998) mod 4 ≡ (402 mod 4 - 7998 mod 4) mod 4.

402 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 402 = 400+2 = 4 ⋅ 100 +2.

7998 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 7998 = 7000+998 = 4 ⋅ 1750 +998.

Somit gilt:

(402 - 7998) mod 4 ≡ (2 - 2) mod 4 ≡ 0 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

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

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

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

Somit gilt:

(81 ⋅ 35) mod 10 ≡ (1 ⋅ 5) mod 10 ≡ 5 mod 10.

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

2: 151²=151¹⁺¹=151¹⋅151¹ ≡ 151⋅151=22801 ≡ 285 mod 433

4: 151⁴=151²⁺²=151²⋅151² ≡ 285⋅285=81225 ≡ 254 mod 433

8: 151⁸=151⁴⁺⁴=151⁴⋅151⁴ ≡ 254⋅254=64516 ≡ 432 mod 433

16: 151¹⁶=151⁸⁺⁸=151⁸⋅151⁸ ≡ 432⋅432=186624 ≡ 1 mod 433

32: 151³²=151¹⁶⁺¹⁶=151¹⁶⋅151¹⁶ ≡ 1⋅1=1 ≡ 1 mod 433

64: 151⁶⁴=151³²⁺³²=151³²⋅151³² ≡ 1⋅1=1 ≡ 1 mod 433

128: 151¹²⁸=151⁶⁴⁺⁶⁴=151⁶⁴⋅151⁶⁴ ≡ 1⋅1=1 ≡ 1 mod 433

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

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

249 = 128+64+32+16+8+1

201²⁴⁹

= 201^{128+64+32+16+8+1}

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

≡ 251 ⋅ 229 ⋅ 42 ⋅ 170 ⋅ 28 ⋅ 201 mod 307
≡ 57479 ⋅ 42 ⋅ 170 ⋅ 28 ⋅ 201 mod 307 ≡ 70 ⋅ 42 ⋅ 170 ⋅ 28 ⋅ 201 mod 307
≡ 2940 ⋅ 170 ⋅ 28 ⋅ 201 mod 307 ≡ 177 ⋅ 170 ⋅ 28 ⋅ 201 mod 307
≡ 30090 ⋅ 28 ⋅ 201 mod 307 ≡ 4 ⋅ 28 ⋅ 201 mod 307
≡ 112 ⋅ 201 mod 307
≡ 22512 mod 307 ≡ 101 mod 307

Es gilt also: 201²⁴⁹ ≡ 101 mod 307

Berechnung des größten gemeinsamen Teilers von 61 und 23

=>61	= 2⋅23 + 15
=>23	= 1⋅15 + 8
=>15	= 1⋅8 + 7
=>8	= 1⋅7 + 1
=>7	= 7⋅1 + 0

also gilt: ggt(61,23)=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= 15-1⋅8	eingesetzt in die Zeile drüber:	1	= 1⋅8 -1⋅(15 -1⋅ 8) = 1⋅8 -1⋅15 +1⋅ 8) = -1⋅15 +2⋅ 8 (=1)
8= 23-1⋅15	eingesetzt in die Zeile drüber:	1	= -1⋅15 +2⋅(23 -1⋅ 15) = -1⋅15 +2⋅23 -2⋅ 15) = 2⋅23 -3⋅ 15 (=1)
15= 61-2⋅23	eingesetzt in die Zeile drüber:	1	= 2⋅23 -3⋅(61 -2⋅ 23) = 2⋅23 -3⋅61 +6⋅ 23) = -3⋅61 +8⋅ 23 (=1)

Es gilt also: ggt(61,23)=1 = -3⋅61 +8⋅23

oder wenn man -3⋅61 auf die linke Seite bringt:

1 +3⋅61 = +8⋅23

Es gilt also: 8⋅23 = 3⋅61 +1

Somit 8⋅23 = 1 mod 61

8 ist also das Inverse von 23 mod 61