Melhor resposta
Diga, 2 ^ 32 + 1 é divisível por m.
Então, 2 ^ 32 = -1 (mod m)
(2 ^ 32) ^ 3 = (- 1) ^ 3 ( mod m)
2 ^ 96 = -1 (mod m)
2 ^ 96 + 1 = 0 (mod m)
Então, a resposta correta é 2 ^ 96 + 1
Resposta
Você não. Por exemplo, veja o que acontece quando x = 12. Você obtém x ^ 2 = 144 = 24 \ cdot 6, mas x não é divisível por 24.
Eu poderia parar aqui, mas isso não seria instrutivo , exceto para dizer que você está errado. Isso não é particularmente útil.
Afinal, posso provar que se k | x ^ 2 (leia isso como “k divide x ^ 2), então k | x para muitos k, incluindo 21, 22, 23, 26, 29 e 30, mas não para 20, 24, 25, 27 ou 28. Qual é a diferença? É aí que as coisas ficam interessantes e instrutivas.
O que sabemos sobre x? Sabemos, pelo Teorema Fundamental da Aritmética, que x pode ser representado exclusivamente como um produto de primos, x = 2 ^ {a\_2} 3 ^ {a\_3} 5 ^ {a\_5} \ cdots. Qualquer um (ou todos, para x = 1) desses valores a\_p podem ser 0 e, de fato, apenas um número finito deles é diferente de zero.
Isso significa que x ^ 2 = 2 ^ { 2a\_2} 3 ^ {2a\_3} 5 ^ {2a\_5} \ cdots. Todos os expoentes agora estão iguais.
O que sabemos sobre k? Pelo mesmo teorema, sabemos que k = 2 ^ {k\_2} 3 ^ {k\_3} 5 ^ {k\_5} \ cdots.
Como isso se relaciona com a divisibilidade? Se k | x ^ 2, isso significa que k\_2 \ leq 2a\_2, k\_3 \ leq 2a\_3, \ dots, k\_p \ leq 2a\_p, \ dots. No entanto, se k | x, isso significa que k\_2 \ leq a\_2, k\_3 \ leq a\_3, \ dots, k\_p \ leq a\_p.
Então, tudo o que realmente temos que fazer para provar se x ^ 2 é divisível por k, então x é divisível por k é mostrar que se k\_p \ leq 2a\_p, então k\_p \ leq a\_p. Como k\_p, a\_p pode ser qualquer inteiro não negativo, então podemos olhar para o problema mais simples: em que condições temos b \ leq 2c implicando b \ leq c?
Basicamente, estamos tentando encontrar valores de b onde a expressão c \ leq 2c não vale para nenhum c. Como não há c , então b = 0 funciona. Para b = 1, somos forçados a ter c = 0 e, portanto, 1 \ não \ leq 2c = 0, então b = 1 funciona.
Mas para b> 1, não trabalhos. Você sempre pode escolher c = b-1
Para trazer isso de volta ao nosso problema, isso significa que podemos dizer k | x ^ 2 \ implica k | x somente quando os expoentes dos primos em k são 0 ou 1. Esses valores de k são chamados de “sem quadrados” porque você não pode dividi-los por um número quadrado.
Então você pode mostrar k | x ^ 2 \ implica k | x se k não tem quadrados.
Para os números que observei acima, 20 é divisível pelo quadrado 4, 24 é divisível pelo quadrado 4, 25 é quadrado, 27 é divisível pelo quadrado 9 , 28 é divisível pelo quadrado 4. Os outros números, 21, 22, 23, 26, 29, 30, são todos livres de quadrados, que você pode verificar se quiser.