primi e divisori

[sqrt2]

Dati n primi distinti $ p_1,...,p_n $ maggiori di 3, dimostrare che $ 2^{p_1...p_n} + 1 $ ha almeno $ 4^n $ divisori.

[dalferro11]

Mmmmh sicuro che non manchi qualcosa?

p(1) = 2
p(2) = 3

2^6 + 1 = 65

I divisori di 65 sono 8 compresi quelli negativi.
Mentre 4^2 = 16
p(1) = 2
p(2) = 5

2^10+1 = 1025 = 5^2*41

I divisori sono 12 compresi i negativi e non 16


[/tex]

[fede90]

sqrt 2 dice "maggiori di 3"!

per esempio con p1=5 e p2=7 abbiamo il numero 2^35+1 che ha 32 divisori, che sono effettivamente piu di 16

[julio14]

Si, dice maggiori di 3, ma se vedi ha modificato il mex alle 14.00 mentre dalferro ha postato alle 8.40....

[fede90]

infatti l'ho notato dopo... sorry

[HiTLeuLeR]

Dati n primi distinti $ p_1,...,p_n $ maggiori di 3, dimostrare che $ 2^{p_1...p_n} + 1 $ ha almeno $ 4^n $ divisori.

Per ogni $ a\in\mathbb{N}^+ $, siano $ \tau(a) $ ed $ \omega(a) $, risp., il numero dei divisori interi positivi ed il numero dei divisori primi naturali di $ a $. Banalmente $ \tau(a) \ge 2^{\omega(a)} $, e si può pertanto riarrangiare il problema nella forma che segue, dove $ \mathfrak{P} $ denota, per comodità, l'insieme di tutti e soli i primi di $ \mathbb{N} $:

"Siano $ n $ un intero positivo e $ p_1, p_2, \ldots, p_n \in \mathfrak{P} $ a due a due distinti e $ \ge 5 $. Allora $ \omega(2^{p_1 p_2 \ldots p_n} + 1) \ge 2n $."

Dim.: la tesi è evidente se $ n=1 $. Infatti, per ogni primo naturale $ p \ge 5 $, vale che i) $ 3 \mid (2^p + 1) $; ii) $ v_3(2^p+1) = 1+v_3(p) = 1 $ e iii) $ 3 < 2^p+1 $. Siano adesso $ p_1, p_2, \ldots, p_{n+1}\in\mathfrak{P} $ a due a due distinti $ \ge 5 $, e $ q = p_1 p_2 \ldots p_{n+1} $. Per via del lemma di Knuth (qui generalizzato), risulta $ \gcd(2^{p_i} + 1, 2^{q/p_i} + 1) = 3 $, per ogni $ i = 1, 2, \ldots, n+1 $, per cui $ 2^{p_i}+1 $ possiede almeno un divisore primo $ r_i\ge 5 $ tale che $ r_i \nmid (2^{q/p_i} + 1) $. D'altra parte, tanto $ 2^{p_i} + 1 $ che $ 2^{q/p_i} + 1 $ dividono $ 2^q + 1 $, e perciò $ \omega(2^q+1) \ge 1+\omega(2^{q/p_i} + 1) $. L'asserto si deduce a questo p.to per induzione, a patto di dimostrare che:

"Esistono almeno un $ i=1, 2, \ldots, n+1 $ e un primo naturale $ t_i \ge 5 $ tale che $ t_i \mid (2^q + 1) $ e $ t_i \nmid (2^{p_i} + 1)(2^{q/p_i} + 1) $."

Dim.: ammettiamo il contrario. Allora in particolare ogni divisore primo naturale $ t \ge 5 $ di $ 2^q + 1 $ è pure un divisore primo naturale di $ (2^{p_1}+1)(2^{q/p_1}+1) $, e pertanto $ t \mid q $ (perché?). Eppure $ v_{p_i}(2^q + 1) \le 1 + v_{p_i}\left((2^{p_1}+1)(2^{q/p_1}+1)\right) $, per ogni $ i = 1, 2, \ldots, n+1 $ (perché?), e $ q \cdot (2^{p_1} + 1)(2^{q/p_1} + 1) < 2^q + 1 $ (induzione), assurdo! Ne segue la tesi.

Come al solito, $ v_p(\cdot) $ indica una valutazione, per ogni $ p\in\mathfrak{P} $.