Um längere Rechnungen zu vermeiden, rechnen wir:

(344 + 355) mod 7 ≡ (344 mod 7 + 355 mod 7) mod 7.

344 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 344 = 350-6 = 7 ⋅ 50 -6 = 7 ⋅ 50 - 7 + 1.

355 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 355 = 350+5 = 7 ⋅ 50 +5.

Somit gilt:

(344 + 355) mod 7 ≡ (1 + 5) mod 7 ≡ 6 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(98 ⋅ 80) mod 11 ≡ (98 mod 11 ⋅ 80 mod 11) mod 11.

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

80 mod 11 ≡ 3 mod 11 kann man relativ leicht bestimmen, weil ja 80 = 77 + 3 = 7 ⋅ 11 + 3 ist.

Somit gilt:

(98 ⋅ 80) mod 11 ≡ (10 ⋅ 3) mod 11 ≡ 30 mod 11 ≡ 8 mod 11.

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

2: 379²=379¹⁺¹=379¹⋅379¹ ≡ 379⋅379=143641 ≡ 560 mod 719

4: 379⁴=379²⁺²=379²⋅379² ≡ 560⋅560=313600 ≡ 116 mod 719

8: 379⁸=379⁴⁺⁴=379⁴⋅379⁴ ≡ 116⋅116=13456 ≡ 514 mod 719

16: 379¹⁶=379⁸⁺⁸=379⁸⋅379⁸ ≡ 514⋅514=264196 ≡ 323 mod 719

32: 379³²=379¹⁶⁺¹⁶=379¹⁶⋅379¹⁶ ≡ 323⋅323=104329 ≡ 74 mod 719

64: 379⁶⁴=379³²⁺³²=379³²⋅379³² ≡ 74⋅74=5476 ≡ 443 mod 719

128: 379¹²⁸=379⁶⁴⁺⁶⁴=379⁶⁴⋅379⁶⁴ ≡ 443⋅443=196249 ≡ 681 mod 719

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

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

133 = 128+4+1

449¹³³

= 449^128+4+1

= 449¹²⁸⋅449⁴⋅449¹

≡ 526 ⋅ 581 ⋅ 449 mod 643
≡ 305606 ⋅ 449 mod 643 ≡ 181 ⋅ 449 mod 643
≡ 81269 mod 643 ≡ 251 mod 643

Es gilt also: 449¹³³ ≡ 251 mod 643

Berechnung des größten gemeinsamen Teilers von 83 und 31

=>83	= 2⋅31 + 21
=>31	= 1⋅21 + 10
=>21	= 2⋅10 + 1
=>10	= 10⋅1 + 0

also gilt: ggt(83,31)=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= 21-2⋅10
10= 31-1⋅21	eingesetzt in die Zeile drüber:	1	= 1⋅21 -2⋅(31 -1⋅ 21) = 1⋅21 -2⋅31 +2⋅ 21) = -2⋅31 +3⋅ 21 (=1)
21= 83-2⋅31	eingesetzt in die Zeile drüber:	1	= -2⋅31 +3⋅(83 -2⋅ 31) = -2⋅31 +3⋅83 -6⋅ 31) = 3⋅83 -8⋅ 31 (=1)

Es gilt also: ggt(83,31)=1 = 3⋅83 -8⋅31

oder wenn man 3⋅83 auf die linke Seite bringt:

1 -3⋅83 = -8⋅31

-8⋅31 = -3⋅83 + 1 |+83⋅31

-8⋅31 + 83⋅31 = -3⋅83 + 83⋅31 + 1

(-8 + 83) ⋅ 31 = (-3 + 31) ⋅ 83 + 1

75⋅31 = 28⋅83 + 1

Es gilt also: 75⋅31 = 28⋅83 +1

Somit 75⋅31 = 1 mod 83

75 ist also das Inverse von 31 mod 83