Um längere Rechnungen zu vermeiden, rechnen wir:

(18003 + 4503) mod 9 ≡ (18003 mod 9 + 4503 mod 9) mod 9.

18003 mod 9 ≡ 3 mod 9 kann man relativ leicht bestimmen, weil ja 18003 = 18000+3 = 9 ⋅ 2000 +3.

4503 mod 9 ≡ 3 mod 9 kann man relativ leicht bestimmen, weil ja 4503 = 4500+3 = 9 ⋅ 500 +3.

Somit gilt:

(18003 + 4503) mod 9 ≡ (3 + 3) mod 9 ≡ 6 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(20 ⋅ 80) mod 6 ≡ (20 mod 6 ⋅ 80 mod 6) mod 6.

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

80 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 80 = 78 + 2 = 13 ⋅ 6 + 2 ist.

Somit gilt:

(20 ⋅ 80) mod 6 ≡ (2 ⋅ 2) mod 6 ≡ 4 mod 6.

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

2: 498²=498¹⁺¹=498¹⋅498¹ ≡ 498⋅498=248004 ≡ 489 mod 569

4: 498⁴=498²⁺²=498²⋅498² ≡ 489⋅489=239121 ≡ 141 mod 569

8: 498⁸=498⁴⁺⁴=498⁴⋅498⁴ ≡ 141⋅141=19881 ≡ 535 mod 569

16: 498¹⁶=498⁸⁺⁸=498⁸⋅498⁸ ≡ 535⋅535=286225 ≡ 18 mod 569

32: 498³²=498¹⁶⁺¹⁶=498¹⁶⋅498¹⁶ ≡ 18⋅18=324 ≡ 324 mod 569

64: 498⁶⁴=498³²⁺³²=498³²⋅498³² ≡ 324⋅324=104976 ≡ 280 mod 569

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

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

78 = 64+8+4+2

202⁷⁸

= 202^64+8+4+2

= 202⁶⁴⋅202⁸⋅202⁴⋅202²

≡ 117 ⋅ 28 ⋅ 157 ⋅ 52 mod 283
≡ 3276 ⋅ 157 ⋅ 52 mod 283 ≡ 163 ⋅ 157 ⋅ 52 mod 283
≡ 25591 ⋅ 52 mod 283 ≡ 121 ⋅ 52 mod 283
≡ 6292 mod 283 ≡ 66 mod 283

Es gilt also: 202⁷⁸ ≡ 66 mod 283

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

=>67	= 1⋅60 + 7
=>60	= 8⋅7 + 4
=>7	= 1⋅4 + 3
=>4	= 1⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(67,60)=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= 4-1⋅3
3= 7-1⋅4	eingesetzt in die Zeile drüber:	1	= 1⋅4 -1⋅(7 -1⋅ 4) = 1⋅4 -1⋅7 +1⋅ 4) = -1⋅7 +2⋅ 4 (=1)
4= 60-8⋅7	eingesetzt in die Zeile drüber:	1	= -1⋅7 +2⋅(60 -8⋅ 7) = -1⋅7 +2⋅60 -16⋅ 7) = 2⋅60 -17⋅ 7 (=1)
7= 67-1⋅60	eingesetzt in die Zeile drüber:	1	= 2⋅60 -17⋅(67 -1⋅ 60) = 2⋅60 -17⋅67 +17⋅ 60) = -17⋅67 +19⋅ 60 (=1)

Es gilt also: ggt(67,60)=1 = -17⋅67 +19⋅60

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

1 +17⋅67 = +19⋅60

Es gilt also: 19⋅60 = 17⋅67 +1

Somit 19⋅60 = 1 mod 67

19 ist also das Inverse von 60 mod 67