Cel mai bun răspuns
Spune, 2 ^ 32 + 1 este divizibil cu m.
Deci, 2 ^ 32 = -1 (mod m)
(2 ^ 32) ^ 3 = (- 1) ^ 3 ( mod m)
2 ^ 96 = -1 (mod m)
2 ^ 96 + 1 = 0 (mod m)
Deci, răspunsul corect este 2 ^ 96 + 1
Răspuns
Nu. De exemplu, uite ce se întâmplă când x = 12. Obții x ^ 2 = 144 = 24 \ cdot 6, dar x nu este divizibil cu 24.
Aș putea să mă opresc aici, dar asta nu ar fi instructiv , cu excepția faptului că spuneți că vă înșelați. Acest lucru nu este deosebit de util.
La urma urmei, pot demonstra că dacă k | x ^ 2 (citiți ca „k împarte x ^ 2), apoi k | x pentru multe k, inclusiv 21, 22, 23, 26, 29 și 30, dar nu pentru 20, 24, 25, 27 sau 28. Care este diferența? Acolo lucrurile devin interesante și instructive.
Ce știm despre x? Știm, prin teorema fundamentală a aritmeticii, că x poate fi reprezentat în mod unic ca produs al primelor, x = 2 ^ {a\_2} 3 ^ {a\_3} 5 ^ {a\_5} \ cdots. Oricare (sau toate, pentru x = 1) dintre acele valori a\_p ar putea fi 0 și, de fapt, doar un număr finit dintre ele sunt diferite de zero.
Asta înseamnă că x ^ 2 = 2 ^ { 2a\_2} 3 ^ {2a\_3} 5 ^ {2a\_5} \ cdots. Toți exponenții sunt acum uniformi.
Ce știm despre k? Prin aceeași teoremă, știm că k = 2 ^ {k\_2} 3 ^ {k\_3} 5 ^ {k\_5} \ cdots.
Cum se leagă acest lucru de divizibilitate? Dacă k | x ^ 2, asta înseamnă că k\_2 \ leq 2a\_2, k\_3 \ leq 2a\_3, \ dots, k\_p \ leq 2a\_p, \ dots. Cu toate acestea, dacă k | x, asta înseamnă că k\_2 \ leq a\_2, k\_3 \ leq a\_3, \ dots, k\_p \ leq a\_p.
Deci tot ce trebuie să facem pentru a demonstra dacă x ^ 2 este divizibil cu k, atunci x este divizibil cu k este arătat că dacă k\_p \ leq 2a\_p, atunci k\_p \ leq a\_p. Deoarece k\_p, a\_p poate fi orice număr întreg negativ, atunci putem privi problema mai simplă: în ce condiții avem b \ leq 2c implicând b \ leq c?
Practic, încercăm să găsim valori din b unde expresia c \ leq 2c nu se menține pentru nici un c. Deoarece nu există c , atunci b = 0 funcționează. Pentru b = 1, suntem forțați să avem c = 0 , deci 1 \ not \ leq 2c = 0, deci b = 1 funcționează.
Dar pentru b> 1, nu funcționează muncă. Puteți alege întotdeauna c = b-1
Pentru a readuce acest lucru la problema noastră, asta înseamnă că putem spune k | x ^ 2 \ implică k | x numai atunci când exponenții primilor din k sunt fie 0, fie 1. Aceste valori ale lui k se numesc „fără pătrat” deoarece nu le puteți împărți la un număr pătrat.
| x ^ 2 \ implică k | x dacă k este fără pătrat.
Pentru numerele la care m-am uitat mai sus, 20 este divizibil cu pătratul 4, 24 este divizibil cu pătratul 4, 25 este pătrat, 27 este divizibil cu pătratul 9 , 28 este divizibil cu pătratul 4. Celelalte numere, 21, 22, 23, 26, 29, 30, sunt fără pătrat, pe care le puteți verifica dacă doriți.