Eulers sats - minsta positiva heltal

Jag ska bestämma den minsta positiva resten när talet 45³² 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å 45¹¹ $\equiv$ 1 mod(34) (visst?)

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

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.

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 Avbryt