Um längere Rechnungen zu vermeiden, rechnen wir:

(265 + 905) mod 9 ≡ (265 mod 9 + 905 mod 9) mod 9.

265 mod 9 ≡ 4 mod 9 kann man relativ leicht bestimmen, weil ja 265 = 270-5 = 9 ⋅ 30 -5 = 9 ⋅ 30 - 9 + 4.

905 mod 9 ≡ 5 mod 9 kann man relativ leicht bestimmen, weil ja 905 = 900+5 = 9 ⋅ 100 +5.

Somit gilt:

(265 + 905) mod 9 ≡ (4 + 5) mod 9 ≡ 9 mod 9 ≡ 0 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

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

72 mod 9 ≡ 0 mod 9 kann man relativ leicht bestimmen, weil ja 72 = 72 + 0 = 8 ⋅ 9 + 0 ist.

98 mod 9 ≡ 8 mod 9 kann man relativ leicht bestimmen, weil ja 98 = 90 + 8 = 10 ⋅ 9 + 8 ist.

Somit gilt:

(72 ⋅ 98) mod 9 ≡ (0 ⋅ 8) mod 9 ≡ 0 mod 9.

Die 128 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: 141¹=141

2: 141²=141¹⁺¹=141¹⋅141¹ ≡ 141⋅141=19881 ≡ 162 mod 313

4: 141⁴=141²⁺²=141²⋅141² ≡ 162⋅162=26244 ≡ 265 mod 313

8: 141⁸=141⁴⁺⁴=141⁴⋅141⁴ ≡ 265⋅265=70225 ≡ 113 mod 313

16: 141¹⁶=141⁸⁺⁸=141⁸⋅141⁸ ≡ 113⋅113=12769 ≡ 249 mod 313

32: 141³²=141¹⁶⁺¹⁶=141¹⁶⋅141¹⁶ ≡ 249⋅249=62001 ≡ 27 mod 313

64: 141⁶⁴=141³²⁺³²=141³²⋅141³² ≡ 27⋅27=729 ≡ 103 mod 313

128: 141¹²⁸=141⁶⁴⁺⁶⁴=141⁶⁴⋅141⁶⁴ ≡ 103⋅103=10609 ≡ 280 mod 313

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

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

242 = 128+64+32+16+2

185²⁴²

= 185^{128+64+32+16+2}

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

≡ 200 ⋅ 114 ⋅ 174 ⋅ 54 ⋅ 407 mod 457
≡ 22800 ⋅ 174 ⋅ 54 ⋅ 407 mod 457 ≡ 407 ⋅ 174 ⋅ 54 ⋅ 407 mod 457
≡ 70818 ⋅ 54 ⋅ 407 mod 457 ≡ 440 ⋅ 54 ⋅ 407 mod 457
≡ 23760 ⋅ 407 mod 457 ≡ 453 ⋅ 407 mod 457
≡ 184371 mod 457 ≡ 200 mod 457

Es gilt also: 185²⁴² ≡ 200 mod 457

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

=>101	= 1⋅88 + 13
=>88	= 6⋅13 + 10
=>13	= 1⋅10 + 3
=>10	= 3⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(101,88)=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= 13-1⋅10	eingesetzt in die Zeile drüber:	1	= 1⋅10 -3⋅(13 -1⋅ 10) = 1⋅10 -3⋅13 +3⋅ 10) = -3⋅13 +4⋅ 10 (=1)
10= 88-6⋅13	eingesetzt in die Zeile drüber:	1	= -3⋅13 +4⋅(88 -6⋅ 13) = -3⋅13 +4⋅88 -24⋅ 13) = 4⋅88 -27⋅ 13 (=1)
13= 101-1⋅88	eingesetzt in die Zeile drüber:	1	= 4⋅88 -27⋅(101 -1⋅ 88) = 4⋅88 -27⋅101 +27⋅ 88) = -27⋅101 +31⋅ 88 (=1)

Es gilt also: ggt(101,88)=1 = -27⋅101 +31⋅88

oder wenn man -27⋅101 auf die linke Seite bringt:

1 +27⋅101 = +31⋅88

Es gilt also: 31⋅88 = 27⋅101 +1

Somit 31⋅88 = 1 mod 101

31 ist also das Inverse von 88 mod 101