Um längere Rechnungen zu vermeiden, rechnen wir:

(2806 + 21007) mod 7 ≡ (2806 mod 7 + 21007 mod 7) mod 7.

2806 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 2806 = 2800+6 = 7 ⋅ 400 +6.

21007 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 21007 = 21000+7 = 7 ⋅ 3000 +7.

Somit gilt:

(2806 + 21007) mod 7 ≡ (6 + 0) mod 7 ≡ 6 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(72 ⋅ 98) mod 5 ≡ (72 mod 5 ⋅ 98 mod 5) mod 5.

72 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 72 = 70 + 2 = 14 ⋅ 5 + 2 ist.

98 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 98 = 95 + 3 = 19 ⋅ 5 + 3 ist.

Somit gilt:

(72 ⋅ 98) mod 5 ≡ (2 ⋅ 3) mod 5 ≡ 6 mod 5 ≡ 1 mod 5.

Die 32 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: 723¹=723

2: 723²=723¹⁺¹=723¹⋅723¹ ≡ 723⋅723=522729 ≡ 400 mod 743

4: 723⁴=723²⁺²=723²⋅723² ≡ 400⋅400=160000 ≡ 255 mod 743

8: 723⁸=723⁴⁺⁴=723⁴⋅723⁴ ≡ 255⋅255=65025 ≡ 384 mod 743

16: 723¹⁶=723⁸⁺⁸=723⁸⋅723⁸ ≡ 384⋅384=147456 ≡ 342 mod 743

32: 723³²=723¹⁶⁺¹⁶=723¹⁶⋅723¹⁶ ≡ 342⋅342=116964 ≡ 313 mod 743

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

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

118 = 64+32+16+4+2

531¹¹⁸

= 531^64+32+16+4+2

= 531⁶⁴⋅531³²⋅531¹⁶⋅531⁴⋅531²

≡ 257 ⋅ 306 ⋅ 293 ⋅ 594 ⋅ 518 mod 653
≡ 78642 ⋅ 293 ⋅ 594 ⋅ 518 mod 653 ≡ 282 ⋅ 293 ⋅ 594 ⋅ 518 mod 653
≡ 82626 ⋅ 594 ⋅ 518 mod 653 ≡ 348 ⋅ 594 ⋅ 518 mod 653
≡ 206712 ⋅ 518 mod 653 ≡ 364 ⋅ 518 mod 653
≡ 188552 mod 653 ≡ 488 mod 653

Es gilt also: 531¹¹⁸ ≡ 488 mod 653

Berechnung des größten gemeinsamen Teilers von 71 und 68

=>71	= 1⋅68 + 3
=>68	= 22⋅3 + 2
=>3	= 1⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(71,68)=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= 3-1⋅2
2= 68-22⋅3	eingesetzt in die Zeile drüber:	1	= 1⋅3 -1⋅(68 -22⋅ 3) = 1⋅3 -1⋅68 +22⋅ 3) = -1⋅68 +23⋅ 3 (=1)
3= 71-1⋅68	eingesetzt in die Zeile drüber:	1	= -1⋅68 +23⋅(71 -1⋅ 68) = -1⋅68 +23⋅71 -23⋅ 68) = 23⋅71 -24⋅ 68 (=1)

Es gilt also: ggt(71,68)=1 = 23⋅71 -24⋅68

oder wenn man 23⋅71 auf die linke Seite bringt:

1 -23⋅71 = -24⋅68

-24⋅68 = -23⋅71 + 1 |+71⋅68

-24⋅68 + 71⋅68 = -23⋅71 + 71⋅68 + 1

(-24 + 71) ⋅ 68 = (-23 + 68) ⋅ 71 + 1

47⋅68 = 45⋅71 + 1

Es gilt also: 47⋅68 = 45⋅71 +1

Somit 47⋅68 = 1 mod 71

47 ist also das Inverse von 68 mod 71