Um längere Rechnungen zu vermeiden, rechnen wir:

(246 + 29998) mod 6 ≡ (246 mod 6 + 29998 mod 6) mod 6.

246 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 246 = 240+6 = 6 ⋅ 40 +6.

29998 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 29998 = 30000-2 = 6 ⋅ 5000 -2 = 6 ⋅ 5000 - 6 + 4.

Somit gilt:

(246 + 29998) mod 6 ≡ (0 + 4) mod 6 ≡ 4 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(34 ⋅ 66) mod 11 ≡ (34 mod 11 ⋅ 66 mod 11) mod 11.

34 mod 11 ≡ 1 mod 11 kann man relativ leicht bestimmen, weil ja 34 = 33 + 1 = 3 ⋅ 11 + 1 ist.

66 mod 11 ≡ 0 mod 11 kann man relativ leicht bestimmen, weil ja 66 = 66 + 0 = 6 ⋅ 11 + 0 ist.

Somit gilt:

(34 ⋅ 66) mod 11 ≡ (1 ⋅ 0) mod 11 ≡ 0 mod 11.

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

2: 231²=231¹⁺¹=231¹⋅231¹ ≡ 231⋅231=53361 ≡ 245 mod 271

4: 231⁴=231²⁺²=231²⋅231² ≡ 245⋅245=60025 ≡ 134 mod 271

8: 231⁸=231⁴⁺⁴=231⁴⋅231⁴ ≡ 134⋅134=17956 ≡ 70 mod 271

16: 231¹⁶=231⁸⁺⁸=231⁸⋅231⁸ ≡ 70⋅70=4900 ≡ 22 mod 271

32: 231³²=231¹⁶⁺¹⁶=231¹⁶⋅231¹⁶ ≡ 22⋅22=484 ≡ 213 mod 271

64: 231⁶⁴=231³²⁺³²=231³²⋅231³² ≡ 213⋅213=45369 ≡ 112 mod 271

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

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

167 = 128+32+4+2+1

147¹⁶⁷

= 147^128+32+4+2+1

= 147¹²⁸⋅147³²⋅147⁴⋅147²⋅147¹

≡ 113 ⋅ 11 ⋅ 120 ⋅ 44 ⋅ 147 mod 227
≡ 1243 ⋅ 120 ⋅ 44 ⋅ 147 mod 227 ≡ 108 ⋅ 120 ⋅ 44 ⋅ 147 mod 227
≡ 12960 ⋅ 44 ⋅ 147 mod 227 ≡ 21 ⋅ 44 ⋅ 147 mod 227
≡ 924 ⋅ 147 mod 227 ≡ 16 ⋅ 147 mod 227
≡ 2352 mod 227 ≡ 82 mod 227

Es gilt also: 147¹⁶⁷ ≡ 82 mod 227

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

=>79	= 1⋅56 + 23
=>56	= 2⋅23 + 10
=>23	= 2⋅10 + 3
=>10	= 3⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(79,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= 10-3⋅3
3= 23-2⋅10	eingesetzt in die Zeile drüber:	1	= 1⋅10 -3⋅(23 -2⋅ 10) = 1⋅10 -3⋅23 +6⋅ 10) = -3⋅23 +7⋅ 10 (=1)
10= 56-2⋅23	eingesetzt in die Zeile drüber:	1	= -3⋅23 +7⋅(56 -2⋅ 23) = -3⋅23 +7⋅56 -14⋅ 23) = 7⋅56 -17⋅ 23 (=1)
23= 79-1⋅56	eingesetzt in die Zeile drüber:	1	= 7⋅56 -17⋅(79 -1⋅ 56) = 7⋅56 -17⋅79 +17⋅ 56) = -17⋅79 +24⋅ 56 (=1)

Es gilt also: ggt(79,56)=1 = -17⋅79 +24⋅56

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

1 +17⋅79 = +24⋅56

Es gilt also: 24⋅56 = 17⋅79 +1

Somit 24⋅56 = 1 mod 79

24 ist also das Inverse von 56 mod 79