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?
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.