Nejlepší odpověď
Řekněte, 2 ^ 32 + 1 je dělitelné m.
Takže, 2 ^ 32 = -1 (mod m)
(2 ^ 32) ^ 3 = (- 1) ^ 3 ( mod m)
2 ^ 96 = -1 (mod m)
2 ^ 96 + 1 = 0 (mod m)
Takže správná odpověď je 2 ^ 96 + 1
Odpověď
Ne. Podívejte se například, co se stane, když x = 12. Získáte x ^ 2 = 144 = 24 \ cdot 6, ale x není dělitelné 24.
Mohl bych se zde zastavit, ale to by nebylo poučné , až na to, že se mýlíš. To není nijak zvlášť užitečné.
Nakonec mohu dokázat, že pokud k | x ^ 2 (přečtěte si to jako „k dělí x ^ 2), pak k | x pro mnoho k, včetně 21, 22, 23, 26, 29 a 30, ale ne pro 20, 24, 25, 27 nebo 28. Jaký je rozdíl? To je místo, kde jsou věci zajímavé a poučné.
Co víme o x? Podle základní věty aritmetiky víme, že x lze jednoznačně reprezentovat jako produkt prvočísel, x = 2 ^ {a\_2} 3 ^ {a\_3} 5 ^ {a\_5} \ cdots. Jakákoli (nebo všechna pro x = 1) z těchto hodnot a\_p může být 0 a ve skutečnosti je pouze konečný počet z nich nenulový.
To znamená, že x ^ 2 = 2 ^ { 2a\_2} 3 ^ {2a\_3} 5 ^ {2a\_5} \ cdots. Všichni exponenti jsou nyní sudí.
Co víme o k? Ze stejné věty víme, že k = 2 ^ {k\_2} 3 ^ {k\_3} 5 ^ {k\_5} \ cdots.
Jak to souvisí s dělitelností? Pokud k | x ^ 2, to znamená, že k\_2 \ leq 2a\_2, k\_3 \ leq 2a\_3, \ dots, k\_p \ leq 2a\_p, \ dots. Pokud však k | x, to znamená, že k\_2 \ leq a\_2, k\_3 \ leq a\_3, \ dots, k\_p \ leq a\_p.
Takže vše, co opravdu musíme udělat, abychom dokázali, zda x ^ 2 je dělitelné k, pak x je dělitelné k je ukázat, že pokud k\_p \ leq 2a\_p, pak k\_p \ leq a\_p. Protože k\_p, a\_p může být jakékoli nezáporné celé číslo, můžeme se podívat na jednodušší problém: za jakých podmínek máme b \ leq 2c implikující b \ leq c?
V podstatě se snažíme najít hodnoty b, kde výraz c \ leq 2c neplatí pro žádné c. Protože neexistuje c , pak b = 0 funguje. Pro b = 1 jsme nuceni mít c = 0 , a tak 1 \ not \ leq 2c = 0, takže b = 1 funguje.
Ale pro b> 1 to neplatí práce. Vždy si můžete vybrat c = b-1
Vrátit to zpět k našemu problému, to znamená, že můžeme říci k | x ^ 2 \ znamená k | x pouze tehdy, když jsou exponenty prvočísel v k buď 0 nebo 1. Tyto hodnoty k se nazývají „bez čtverců“, protože je nemůžete rozdělit čtvercovým číslem.
Takže můžete ukázat k | x ^ 2 \ znamená k | x, pokud k je bez čtverce.
U čísel, která jsem sledoval výše, je 20 dělitelných čtvercem 4, 24 je dělitelné čtvercem 4, 25 je čtverce, 27 je dělitelné čtvercem 9 , 28 je dělitelné čtvercem 4. Ostatní čísla, 21, 22, 23, 26, 29, 30, jsou všechna bez čtverců, což můžete podle potřeby zkontrolovat.