7^221 mod 184 (IBitte mit Lösungsweg)

Question

7^221 mod 184

Der Rest soll berechnet werden. Wenn möglich bitte mit Lösungsweg ,da ich keine Ahnung habe wie ich es lösen soll

Answer 1

7^221 = 7 * 7^220 = 7 * 49^110 = 7 * 2401^55

2401 mod 184 = 9

7 * 9^55 = 7 * 9 * 9^54 = 7 * 9 * 81^27 = 7 * 9 * 81 * 81^26 = 7 * 9 * 81 * 6561^13
7 * 9 * 81 mod 184 = 5103 mod 184 = 135

6561 mod 184 = 121

135 * 121^13 = 135 * 121 * 121^12 = 135 * 121 * 14641^6

135 * 121 mod 184 = 143
14641 mod 184 = 105

143 * 105^6 = 143 * 11025^3

11025 mod 184 = 169

143 * 169^3 = 143 * 169 * 169^2 = 143 * 169 * 28561

143 * 169 mod 184 = 63
28561 mod 184 = 41

63 * 41 = 2583

2583 mod 184 = 7


Daher ist 7^221 mod 184 = 7

Comments

Klasse! Vielen herzlichen Dank! Jedoch versteh ich ein zwei Dinge nicht. und zwar

oben ganz am Anfang wendest du das Potenzgesetz bei der 7 bis 2401 an und machst dann dies modulo 184 und unten 6561 mod 184 wann weiß ich das ich eine zahl dann modulo 184 machen muss?

---

Du kannst jeden Faktor > 184 mod 184 rechnen.

Das heißt sobald ich Faktoren habe die größer sind wende ich hier den Modulo an.

Brucybabe hat auch einen guten Ansatz. Während ich nur die 2 im Exponenten herausziehe hat Brucybabe das auch mit der 3 gemacht. Ich verwende meist nur die 2 weil ich zahlen leicht im Kopf quadrieren kann.

Answer 2

$$\lambda$$ bezeichne die Carmichaelfunktion.

Es ist $$\lambda(184)=\lambda(8)\lambda(23)=2\cdot 22=44$$.

Also ist $$7^{221}\equiv 7^{5\cdot 44 +1}\equiv 7 \mod 184$$

Answer 3

\( 7^4 = 2401 \equiv 9 \mod 184 \), also \( ^{221}\equiv 7 \cdot 7^{4\cdot 55} \equiv 7 \cdot 3^{11 \cdot 2} \)

Es ist

$$3^{11}=177147\equiv -45 \mod 184 \text{ und } 45^2=2025\equiv 1 \mod 184$$

Gesamt: $$7^{221} \equiv 7 \cdot 3^{11\cdot 2} \equiv 7 \cdot (-45)^2\equiv 7 \mod 184$$