Hur löser man ekvationen i restklassringen m.h.a Eulers satts och/eller Fermats lilla sats?

Hej! Jag behöver hjälp med att lösa följande ekvation:

^{$x^{17} \equiv 37 (m o d 221)$}

^{Är det någon snäll själ som kan visa mig steg för steg hur man löser uppgiften? I min bok de hoppar över alla steg därför har jag svår att förstå deras uträkning. Jag vet att man använder Euler sats, men hänger inte riktigt med på hur de tillämpar satsen.}

^{Tacksam för all hjälp!}

Eftersom att 37 och 221 är relativt prima kommer du få en lösning $x = 37^{17^{-1}}$ , där $17^{-1}$ är inversen till 17 i ringen $\mathbb{Z}_{\phi(221)}$ . Beroende på din kurslitteratur så kanske detta direkt följer av en sats någonstans i boken eller så behöver du göra några steg där du använder bl.a. Eulers sats. Kanske vore det en bra idé om du kort redogjorde för bokens lösning och sen förklarar var någonstans du blir förvirrad?

EDIT: Ändrade ett fel (se Skafts anmärkning nedan).

Freewheeling skrev:
Eftersom att 37 och 221 är relativt prima kommer du få en lösning $x = 37^{17^{-1}}$ , där $17^{-1}$ är inversen till 17 i ringen $\mathbb{Z}_{221}$ .

17 har ingen invers mod 221, eftersom 221 = 13*17.

Skaft skrev:
Freewheeling skrev:
Eftersom att 37 och 221 är relativt prima kommer du få en lösning $x = 37^{17^{-1}}$ , där $17^{-1}$ är inversen till 17 i ringen $\mathbb{Z}_{221}$ .

17 har ingen invers mod 221, eftersom 221 = 13*17.

Japp, skrev fel! Menade inversen till 17 i ringen $\mathbb{Z}_{\phi(221)}$ , där $\phi$ är Eulers fi-funktion.

Svara

Visa senaste svar