104) Aumento esponenziale di divisori

[spugna]

Siano $p_1,p_2,..p_n$ numeri primi diversi tra loro e maggiori di 3. Detto $z$ il loro prodotto, si dimostri che $2^z+1$ ha almeno $4^n$ divisori

P.S.: non conosco la soluzione, ma mi sembra alla vostra portata... (non alla mia)

[xXStephXx]

Io per ora ho capito solo che $ z $ è dispari, quindi $ 2^z+1 $ è scomponibile in $ (2+1)(2^{z-1}-2^{z-2}+2^{z-3}-...+1) $. A sua volta lo posso scomporre in $ (2+1)(2^{z-2}+2^{z-4}+2^{z-6}+...+2+1) $. Volendo potrei scomporre ancora però non saprei proprio cosa fare xD

[exodd]

Ancora non l'ho risolto, ma ci sono quasi..
Un po' di hint

Hint 1

Testo nascosto:

$ (2^{p_i}+1,2^{p_j}+1)=3 $

Hint 2

Testo nascosto:

se $ n=\sum p_i^{a_i} $, allora il numero di divisori di $ n $ è $ \prod (a_i+1) $

Hint 3

Testo nascosto:

se $ p|z $, allora $ 2^p+1|2^z+1 $

[jordan]

Chiedo per l'ennesima volta di non postare problemi alla staffetta di cui non si conosce la soluzione.

Ps. Per questo caso lascia stare, perchè la soluzione olimpica esiste ed è anche abbastanza conosciuta..

[jordan]

Siano $p_1,p_2,..p_n$ numeri primi diversi tra loro e maggiori di 3. Detto $z$ il loro prodotto, si dimostri che $2^z+1$ ha almeno $4^n$ divisori

P.S.: non conosco la soluzione, ma mi sembra alla vostra portata... (non alla mia)

Dimostramo la tesi per induzione. Se $\omega(z)=1, |\mu(z)|=1$ allora $1<3<\frac{2^z+1}{3}<2^z+1$ dividono $4$ per cui $\sigma_0(2^z+1)\ge 4$.

Supponiamo che abbiamo dimostrato che dato qualunque $z\in \mathbb{N}, |\mu(z)|=1, \omega(z)=n, \text{lpf}(z)\ge 5$ valga $\omega_0(2^z+1)\ge 4^{\omega(z)}$.

Fissato un qualunque $z$, dimostriamo che la tesi vale anche per $zp$, dove $p\ge 5$ è un primo tale che $p\nmid z$.
Abbiamo $\upsilon_3(2^{zp}+1)=\upsilon_3(3)+\upsilon_3(zp)=1$, e che $\text{gcd}(2^z+1, 2^p+1)\mid$ $ \text{gcd}(2^{2z}-1, 2^{2p}-1)=2^{\text{gcd}(2z,2p)}-1=2^2-1$: questo significa che $\text{gcd}(2^z+1,\frac{2^p+1}{3})=1$.

Notiamo anche che $(2^z+1)^2(\frac{2^p+1}{3})^2=\frac{1}{9}(2^{2z}+2^{z+1}+1)(2^{2p}+2^{p+1}+1)< \frac{1}{9}2^{2z+1}2^{2p+1}< 2^{2z+2p} < 2^{zp}+1$. implica che se $d\mid (2^z+1)(\frac{2^p+1}{3})\mid 2^z+1$ allora anche $\frac{2^z+1}{d} \mid 2^z+1$ ed e' distinto da tutti gli altri divisori di $(2^z+1)(\frac{2^p+1}{3})$.

Dato che $2^z+1\mid 2^{zp}+1$ e anche $\frac{2^p+1}{3}\mid 2^{zp}+1$, possiamo allora concludere che $\sigma_0(2^{zp}+1) \ge 2\sigma_0(2^z+1) \sigma_0(\frac{2^p+1}{3})\ge 4^{\omega(z)+1}$. []