Najlepsza odpowiedź
Powiedz, 2 ^ 32 + 1 jest podzielne przez m.
Zatem 2 ^ 32 = -1 (mod m)
(2 ^ 32) ^ 3 = (- 1) ^ 3 ( mod m)
2 ^ 96 = -1 (mod m)
2 ^ 96 + 1 = 0 (mod m)
A więc prawidłowa odpowiedź to 2 ^ 96 + 1
Odpowiedź
Nie. Na przykład spójrz, co się stanie, gdy x = 12. Otrzymasz x ^ 2 = 144 = 24 \ cdot 6, ale x nie jest podzielne przez 24.
Mógłbym na tym poprzestać, ale to nie byłoby pouczające z wyjątkiem stwierdzenia, że się mylisz. Nie jest to szczególnie pomocne.
W końcu mogę to udowodnić, jeśli k | x ^ 2 (czytaj jako „k dzieli x ^ 2), a następnie k | x dla wielu k, w tym 21, 22, 23, 26, 29 i 30, ale nie dla 20, 24, 25, 27 lub 28. Jaka jest różnica? W tym miejscu sprawy stają się interesujące i pouczające.
Co wiemy o x? Wiemy, zgodnie z Fundamentalnym twierdzeniem arytmetyki, że x można jednoznacznie przedstawić jako iloczyn liczb pierwszych, x = 2 ^ {a\_2} 3 ^ {a\_3} 5 ^ {a\_5} \ cdots. Każda (lub wszystkie, dla x = 1) z tych wartości a\_p mogą wynosić 0, aw rzeczywistości tylko skończona ich liczba jest różna od zera.
Oznacza to, że x ^ 2 = 2 ^ { 2a\_2} 3 ^ {2a\_3} 5 ^ {2a\_5} \ cdots. Wszystkie wykładniki są teraz parzyste.
Co wiemy o k? Z tego samego twierdzenia wiemy, że k = 2 ^ {k\_2} 3 ^ {k\_3} 5 ^ {k\_5} \ cdots.
Jak to się ma do podzielności? Jeśli k | x ^ 2, czyli k\_2 \ leq 2a\_2, k\_3 \ leq 2a\_3, \ dots, k\_p \ leq 2a\_p, \ dots. Jeśli jednak k | x, to znaczy, że k\_2 \ leq a\_2, k\_3 \ leq a\_3, \ dots, k\_p \ leq a\_p.
Więc wszystko, co naprawdę musimy zrobić, aby udowodnić, że x ^ 2 jest podzielne przez k, a następnie x jest podzielne przez k pokazuje, że jeśli k\_p \ leq 2a\_p, to k\_p \ leq a\_p. Ponieważ k\_p, a\_p może być dowolną nieujemną liczbą całkowitą, możemy spojrzeć na prostszy problem: w jakich warunkach mamy b \ leq 2c implikujące b \ leq c?
Zasadniczo próbujemy znaleźć wartości z b, gdzie wyrażenie c \ leq 2c nie zachowuje się dla żadnego c. Ponieważ nie ma c , to b = 0 działa. Dla b = 1, jesteśmy zmuszeni mieć c = 0 , a więc 1 \ not \ leq 2c = 0, więc b = 1 działa.
Ale dla b> 1 nie praca. Zawsze możesz wybrać c = b-1
Wracając do naszego problemu, oznacza to, że możemy powiedzieć k | x ^ 2 \ implikuje k | x tylko wtedy, gdy wykładniki liczb pierwszych w k wynoszą 0 lub 1. Te wartości k nazywane są „bez kwadratów”, ponieważ nie można ich podzielić przez liczbę kwadratową.
Więc możesz pokazać k | x ^ 2 \ implikuje k | x jeśli k jest wolne od kwadratu.
Dla liczb, które sprawdziłem powyżej, 20 jest podzielne przez kwadrat 4, 24 jest podzielne przez kwadrat 4, 25 to kwadrat, 27 jest podzielne przez kwadrat 9 , 28 jest podzielne przez kwadrat 4. Pozostałe liczby, 21, 22, 23, 26, 29, 30 są bez kwadratów, co możesz sprawdzić, jeśli chcesz.