Meilleure réponse
Dites, 2 ^ 32 + 1 est divisible par m.
Donc, 2 ^ 32 = -1 (mod m)
(2 ^ 32) ^ 3 = (- 1) ^ 3 ( mod m)
2 ^ 96 = -1 (mod m)
2 ^ 96 + 1 = 0 (mod m)
Donc, la bonne réponse vaut 2 ^ 96 + 1
Réponse
Vous ne le faites pas. Par exemple, regardez ce qui se passe lorsque x = 12. Vous obtenez x ^ 2 = 144 = 24 \ cdot 6 mais x nest pas divisible par 24.
Je pourrais marrêter ici, mais ce ne serait pas instructif , sauf pour dire que vous vous trompez. Ce n’est pas particulièrement utile.
Après tout, je peux prouver que si k | x ^ 2 (lire que «k divise x ^ 2), alors k | x pour un grand nombre de k, dont 21, 22, 23, 26, 29 et 30, mais pas pour 20, 24, 25, 27 ou 28. Quelle est la différence? C’est là que les choses deviennent intéressantes et instructives.
Que savons-nous de x? Nous savons, par le théorème fondamental de larithmétique, que x peut être représenté uniquement comme un produit de nombres premiers, x = 2 ^ {a\_2} 3 ^ {a\_3} 5 ^ {a\_5} \ cdots. Nimporte laquelle (ou toutes, pour x = 1) de ces valeurs a\_p pourraient être égales à 0, et en fait, seul un nombre fini dentre elles sont non nulles.
Cela signifie que x ^ 2 = 2 ^ { 2a\_2} 3 ^ {2a\_3} 5 ^ {2a\_5} \ cdots. Tous les exposants sont maintenant pairs.
Que savons-nous de k? Par le même théorème, nous savons que k = 2 ^ {k\_2} 3 ^ {k\_3} 5 ^ {k\_5} \ cdots.
Comment cela est-il lié à la divisibilité? Si k | x ^ 2, cela signifie que k\_2 \ leq 2a\_2, k\_3 \ leq 2a\_3, \ dots, k\_p \ leq 2a\_p, \ dots. Cependant, si k | x, cela signifie que k\_2 \ leq a\_2, k\_3 \ leq a\_3, \ dots, k\_p \ leq a\_p.
Donc tout ce que nous avons vraiment à faire pour prouver si x ^ 2 est divisible par k, alors x est divisible par k est montrer que si k\_p \ leq 2a\_p, alors k\_p \ leq a\_p. Puisque k\_p, a\_p peut être nimporte quel entier non négatif, alors nous pouvons regarder le problème plus simple: dans quelles conditions avons-nous b \ leq 2c impliquant b \ leq c?
Fondamentalement, nous essayons de trouver des valeurs de b où lexpression c \ leq 2c ne vaut pour aucun c. Puisquil ny a pas de c , alors b = 0 fonctionne. Pour b = 1, nous sommes obligés davoir c = 0 , et donc 1 \ not \ leq 2c = 0, donc b = 1 fonctionne.
Mais pour b> 1, ce nest pas le cas travail. Vous pouvez toujours choisir c = b-1
Pour ramener cela à notre problème, cela signifie que nous pouvons dire k | x ^ 2 \ implique k | x uniquement lorsque les exposants des nombres premiers dans k sont 0 ou 1. Ces valeurs de k sont appelées «sans carré» car vous ne pouvez pas les diviser par un nombre carré.
Vous pouvez donc afficher k | x ^ 2 \ implique k | x si k est sans carré.
Pour les nombres que jai regardés ci-dessus, 20 est divisible par le carré 4, 24 est divisible par le carré 4, 25 est carré, 27 est divisible par le carré 9 , 28 est divisible par le carré 4. Les autres nombres, 21, 22, 23, 26, 29, 30, sont tous sans carré, ce que vous pouvez vérifier si vous le souhaitez.