Um längere Rechnungen zu vermeiden, rechnen wir:

(504 + 495) mod 5 ≡ (504 mod 5 + 495 mod 5) mod 5.

504 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 504 = 500+4 = 5 ⋅ 100 +4.

495 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 495 = 400+95 = 5 ⋅ 80 +95.

Somit gilt:

(504 + 495) mod 5 ≡ (4 + 0) mod 5 ≡ 4 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(68 ⋅ 69) mod 4 ≡ (68 mod 4 ⋅ 69 mod 4) mod 4.

68 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 68 = 68 + 0 = 17 ⋅ 4 + 0 ist.

69 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 69 = 68 + 1 = 17 ⋅ 4 + 1 ist.

Somit gilt:

(68 ⋅ 69) mod 4 ≡ (0 ⋅ 1) mod 4 ≡ 0 mod 4.

Die 64 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: 509¹=509

2: 509²=509¹⁺¹=509¹⋅509¹ ≡ 509⋅509=259081 ≡ 350 mod 547

4: 509⁴=509²⁺²=509²⋅509² ≡ 350⋅350=122500 ≡ 519 mod 547

8: 509⁸=509⁴⁺⁴=509⁴⋅509⁴ ≡ 519⋅519=269361 ≡ 237 mod 547

16: 509¹⁶=509⁸⁺⁸=509⁸⋅509⁸ ≡ 237⋅237=56169 ≡ 375 mod 547

32: 509³²=509¹⁶⁺¹⁶=509¹⁶⋅509¹⁶ ≡ 375⋅375=140625 ≡ 46 mod 547

64: 509⁶⁴=509³²⁺³²=509³²⋅509³² ≡ 46⋅46=2116 ≡ 475 mod 547

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

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

235 = 128+64+32+8+2+1

357²³⁵

= 357^{128+64+32+8+2+1}

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

≡ 724 ⋅ 100 ⋅ 10 ⋅ 508 ⋅ 677 ⋅ 357 mod 773
≡ 72400 ⋅ 10 ⋅ 508 ⋅ 677 ⋅ 357 mod 773 ≡ 511 ⋅ 10 ⋅ 508 ⋅ 677 ⋅ 357 mod 773
≡ 5110 ⋅ 508 ⋅ 677 ⋅ 357 mod 773 ≡ 472 ⋅ 508 ⋅ 677 ⋅ 357 mod 773
≡ 239776 ⋅ 677 ⋅ 357 mod 773 ≡ 146 ⋅ 677 ⋅ 357 mod 773
≡ 98842 ⋅ 357 mod 773 ≡ 671 ⋅ 357 mod 773
≡ 239547 mod 773 ≡ 690 mod 773

Es gilt also: 357²³⁵ ≡ 690 mod 773

Berechnung des größten gemeinsamen Teilers von 59 und 26

=>59	= 2⋅26 + 7
=>26	= 3⋅7 + 5
=>7	= 1⋅5 + 2
=>5	= 2⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(59,26)=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-2⋅2
2= 7-1⋅5	eingesetzt in die Zeile drüber:	1	= 1⋅5 -2⋅(7 -1⋅ 5) = 1⋅5 -2⋅7 +2⋅ 5) = -2⋅7 +3⋅ 5 (=1)
5= 26-3⋅7	eingesetzt in die Zeile drüber:	1	= -2⋅7 +3⋅(26 -3⋅ 7) = -2⋅7 +3⋅26 -9⋅ 7) = 3⋅26 -11⋅ 7 (=1)
7= 59-2⋅26	eingesetzt in die Zeile drüber:	1	= 3⋅26 -11⋅(59 -2⋅ 26) = 3⋅26 -11⋅59 +22⋅ 26) = -11⋅59 +25⋅ 26 (=1)

Es gilt also: ggt(59,26)=1 = -11⋅59 +25⋅26

oder wenn man -11⋅59 auf die linke Seite bringt:

1 +11⋅59 = +25⋅26

Es gilt also: 25⋅26 = 11⋅59 +1

Somit 25⋅26 = 1 mod 59

25 ist also das Inverse von 26 mod 59