Um längere Rechnungen zu vermeiden, rechnen wir:

(1201 + 1600) mod 4 ≡ (1201 mod 4 + 1600 mod 4) mod 4.

1201 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 1201 = 1200+1 = 4 ⋅ 300 +1.

1600 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 1600 = 1600+0 = 4 ⋅ 400 +0.

Somit gilt:

(1201 + 1600) mod 4 ≡ (1 + 0) mod 4 ≡ 1 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(91 ⋅ 16) mod 7 ≡ (91 mod 7 ⋅ 16 mod 7) mod 7.

91 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 91 = 91 + 0 = 13 ⋅ 7 + 0 ist.

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

Somit gilt:

(91 ⋅ 16) mod 7 ≡ (0 ⋅ 2) mod 7 ≡ 0 mod 7.

Die 16 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: 321¹=321

2: 321²=321¹⁺¹=321¹⋅321¹ ≡ 321⋅321=103041 ≡ 32 mod 431

4: 321⁴=321²⁺²=321²⋅321² ≡ 32⋅32=1024 ≡ 162 mod 431

8: 321⁸=321⁴⁺⁴=321⁴⋅321⁴ ≡ 162⋅162=26244 ≡ 384 mod 431

16: 321¹⁶=321⁸⁺⁸=321⁸⋅321⁸ ≡ 384⋅384=147456 ≡ 54 mod 431

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

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

222 = 128+64+16+8+4+2

778²²²

= 778^{128+64+16+8+4+2}

= 778¹²⁸⋅778⁶⁴⋅778¹⁶⋅778⁸⋅778⁴⋅778²

≡ 283 ⋅ 77 ⋅ 527 ⋅ 753 ⋅ 850 ⋅ 221 mod 941
≡ 21791 ⋅ 527 ⋅ 753 ⋅ 850 ⋅ 221 mod 941 ≡ 148 ⋅ 527 ⋅ 753 ⋅ 850 ⋅ 221 mod 941
≡ 77996 ⋅ 753 ⋅ 850 ⋅ 221 mod 941 ≡ 834 ⋅ 753 ⋅ 850 ⋅ 221 mod 941
≡ 628002 ⋅ 850 ⋅ 221 mod 941 ≡ 355 ⋅ 850 ⋅ 221 mod 941
≡ 301750 ⋅ 221 mod 941 ≡ 630 ⋅ 221 mod 941
≡ 139230 mod 941 ≡ 903 mod 941

Es gilt also: 778²²² ≡ 903 mod 941

Berechnung des größten gemeinsamen Teilers von 101 und 56

=>101	= 1⋅56 + 45
=>56	= 1⋅45 + 11
=>45	= 4⋅11 + 1
=>11	= 11⋅1 + 0

also gilt: ggt(101,56)=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= 45-4⋅11
11= 56-1⋅45	eingesetzt in die Zeile drüber:	1	= 1⋅45 -4⋅(56 -1⋅ 45) = 1⋅45 -4⋅56 +4⋅ 45) = -4⋅56 +5⋅ 45 (=1)
45= 101-1⋅56	eingesetzt in die Zeile drüber:	1	= -4⋅56 +5⋅(101 -1⋅ 56) = -4⋅56 +5⋅101 -5⋅ 56) = 5⋅101 -9⋅ 56 (=1)

Es gilt also: ggt(101,56)=1 = 5⋅101 -9⋅56

oder wenn man 5⋅101 auf die linke Seite bringt:

1 -5⋅101 = -9⋅56

-9⋅56 = -5⋅101 + 1 |+101⋅56

-9⋅56 + 101⋅56 = -5⋅101 + 101⋅56 + 1

(-9 + 101) ⋅ 56 = (-5 + 56) ⋅ 101 + 1

92⋅56 = 51⋅101 + 1

Es gilt also: 92⋅56 = 51⋅101 +1

Somit 92⋅56 = 1 mod 101

92 ist also das Inverse von 56 mod 101