Um längere Rechnungen zu vermeiden, rechnen wir:

(152 + 2405) mod 8 ≡ (152 mod 8 + 2405 mod 8) mod 8.

152 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 152 = 160-8 = 8 ⋅ 20 -8 = 8 ⋅ 20 - 8 + 0.

2405 mod 8 ≡ 5 mod 8 kann man relativ leicht bestimmen, weil ja 2405 = 2400+5 = 8 ⋅ 300 +5.

Somit gilt:

(152 + 2405) mod 8 ≡ (0 + 5) mod 8 ≡ 5 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(16 ⋅ 73) mod 8 ≡ (16 mod 8 ⋅ 73 mod 8) mod 8.

16 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 16 = 16 + 0 = 2 ⋅ 8 + 0 ist.

73 mod 8 ≡ 1 mod 8 kann man relativ leicht bestimmen, weil ja 73 = 72 + 1 = 9 ⋅ 8 + 1 ist.

Somit gilt:

(16 ⋅ 73) mod 8 ≡ (0 ⋅ 1) mod 8 ≡ 0 mod 8.

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

2: 490²=490¹⁺¹=490¹⋅490¹ ≡ 490⋅490=240100 ≡ 43 mod 523

4: 490⁴=490²⁺²=490²⋅490² ≡ 43⋅43=1849 ≡ 280 mod 523

8: 490⁸=490⁴⁺⁴=490⁴⋅490⁴ ≡ 280⋅280=78400 ≡ 473 mod 523

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

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

251 = 128+64+32+16+8+2+1

322²⁵¹

= 322^{128+64+32+16+8+2+1}

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

≡ 104 ⋅ 25 ⋅ 516 ⋅ 396 ⋅ 104 ⋅ 5 ⋅ 322 mod 521
≡ 2600 ⋅ 516 ⋅ 396 ⋅ 104 ⋅ 5 ⋅ 322 mod 521 ≡ 516 ⋅ 516 ⋅ 396 ⋅ 104 ⋅ 5 ⋅ 322 mod 521
≡ 266256 ⋅ 396 ⋅ 104 ⋅ 5 ⋅ 322 mod 521 ≡ 25 ⋅ 396 ⋅ 104 ⋅ 5 ⋅ 322 mod 521
≡ 9900 ⋅ 104 ⋅ 5 ⋅ 322 mod 521 ≡ 1 ⋅ 104 ⋅ 5 ⋅ 322 mod 521
≡ 104 ⋅ 5 ⋅ 322 mod 521
≡ 520 ⋅ 322 mod 521
≡ 167440 mod 521 ≡ 199 mod 521

Es gilt also: 322²⁵¹ ≡ 199 mod 521

Berechnung des größten gemeinsamen Teilers von 67 und 24

=>67	= 2⋅24 + 19
=>24	= 1⋅19 + 5
=>19	= 3⋅5 + 4
=>5	= 1⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(67,24)=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= 5-1⋅4
4= 19-3⋅5	eingesetzt in die Zeile drüber:	1	= 1⋅5 -1⋅(19 -3⋅ 5) = 1⋅5 -1⋅19 +3⋅ 5) = -1⋅19 +4⋅ 5 (=1)
5= 24-1⋅19	eingesetzt in die Zeile drüber:	1	= -1⋅19 +4⋅(24 -1⋅ 19) = -1⋅19 +4⋅24 -4⋅ 19) = 4⋅24 -5⋅ 19 (=1)
19= 67-2⋅24	eingesetzt in die Zeile drüber:	1	= 4⋅24 -5⋅(67 -2⋅ 24) = 4⋅24 -5⋅67 +10⋅ 24) = -5⋅67 +14⋅ 24 (=1)

Es gilt also: ggt(67,24)=1 = -5⋅67 +14⋅24

oder wenn man -5⋅67 auf die linke Seite bringt:

1 +5⋅67 = +14⋅24

Es gilt also: 14⋅24 = 5⋅67 +1

Somit 14⋅24 = 1 mod 67

14 ist also das Inverse von 24 mod 67