Esiste questo numero?

[pi_greco_quadro]

Determinare se esiste un numero $ \displaystyle n $ avente esattamente $ 2006 $ divisori primi distinti e tale che
$ \displaystyle n\mid 2^n + 1 $

Bonus question (che mi è venuta in mente risolvendolo): dire, se assegnato $ k $ naturale, esiste un siffatto numero avente esattamente $ k $ divisori primi distinti.

[piever]

Tale $ n $ esiste per ogni $ k $ intero positivo.

Per $ k=1 $ esiste $ n $

Infatti $ 3|2^3+1 $

Ora dimostriamo che se esiste per $ k $ allora esiste anche per $ k+1 $

D'ora in poi tutte le lettere usate indicano numeri interi positivi.

Supponiamo per assurdo che esista per $ k $ ma non per $ k+1 $

Abbiamo che $ n*j=2^n+1 $

Ora si dimostra facilmente con il binomio di Newton che $ j*n^2*m=2^{n^2}+1 $ con $ (m,n)=1 $ e $ m>1 $ se $ n>2 $ (che è vero, visto che $ n $ è diviso da almeno un primo dispari).

Sia $ p $ un divisore primo di $ m $

Abbiamo che $ n^2*p|2^{n^2*p}+1 $ contraddicendo l'ipotesi.

Quindi esiste $ n $ per ogni $ k $ intero positivo.

Volendo essere pignoli, esiste $ n $ anche per $ k=0 $ visto che $ 1|2+1 $

CVD

[pi_greco_quadro]

In alternativa osserviamo che $ \displaystyle 3^a\mid 2^{3^a}+1 $ per ogni $ \displaystyle a $ naturale. Quindi possiamo scegliere $ \displaystyle a $ sufficientemente grande tale che $ \displaystyle 2^{3^a} $ abbia $ \displaystyle k-1 $ divisori primi differenti da $ \displaystyle 3 $. A questo punto, siano $ \displaystyle p_1, p_2,\cdots, p_{k-1} $ tali divisori. Noi sappiamo $ \displaystyle 2^{3^a}\equiv -1 \pmod {p_i}\Rightarrow 2^{3^a*p_1*p_2*\cdots*p_{k-1}}\equiv -1\pmod {p_i} $ (infatti $ \displaystyle p_1*p_2*\cdots*p_{k-1} $ è dispari).
Scegliamo quindi $ \displaystyle n=3^{a}*p_1*p_2*\cdots*p_{k-1} $ e abbiamo concluso.

[Simo_the_wolf]

Uhm...Scusa pi_greco, ma chi ti dice che puoi scegliere un $ a $ con quella proprietà??

[pi_greco_quadro]

fondamentalmente l'idea cui ho pensato io è questa...

posto che $ \displaystyle 2^{3^j}+1\mid 2^{3^{j+1}}+1 $ allora $ \displaystyle 2^{3^{j+1}}+1 $ ha almeno un divisore primo in più di $ \displaystyle 2^{3^{j}}+1 $ diverso da 3. In questo modo posso pensare di trovare $ \displaystyle a $ con le proprietà richieste