2 svar
75 visningar
Amanda1234567 20 – Fd. Medlem
Postad: 19 apr 2023 07:41

Eulers sats - minsta positiva heltal

Jag ska bestämma den minsta positiva resten när talet 4532 delas med 34.

Då talet 34 inte är primtal så kan vi använda Eulers sats.

Den relativa prima är ϕ(34)=11 (eller hur?) så 45111 mod(34) (visst?)

Är början på min lösning rätt? Hur ser lösningen steg för steg? 

Laguna Online 30496
Postad: 19 apr 2023 09:44

Python håller inte med: jag skrev in (45**11)%34 och det blev 29.

Däremot är (45**16)%34 = 1.

Jag har inte funderat på det matematiska.

R0BRT 70
Postad: 19 apr 2023 16:05

Dela upp 34 i primtalsfaktorer: 34 = 2 * 17.
Du kan lösa 45^32 mod 2 genom att notera att 45 är udda så då kommer också 45^32 vara udda.
För att lösa 45^32 mod 17 kan du använda Fermats lilla sats eftersom 17 är ett primtal. Notera att (45^16)^2=45^32.
Du kan sedan få fram lösningen på 45^32 mod 34 genom att använda en kinesiska restklassatsen.

Svara
Close