Un problema di 25 anni, ma sempre interessante
Un problema di 25 anni, ma sempre interessante
Determinare tutti gli $n$ tali che $$n^2 \mid 2^n +1$$
Re: Un problema di 25 anni, ma sempre interessante
Osservazione: se $3\mid n$ allora $3^2\nmid n$.
Infatti deve valere che $2v_3(n)\le v_3(2^n+1)=v_3(2+1)+v_3(n)$ , dove nell'ultimo passaggio abbiamo usato LTE.
Quindi svolgendo otteniamo $v_3(n)=1$ che è ciò vhe volevamo dimostrare.
La tesi implica che $n\mid 2^n+1$.
In prima battuta osserviamo che $(2,n)=1$ (altrimenti avremmo che un pari divide un dispari, assurdo). $2$ quindi non compare nella fattorizzazione di $n$
Enunciamo ora il Lemma di Drago: (me lo fece notare in forma quasi uguale in un problema di un annetto fa
)
$a^n\equiv -1 (p) \Rightarrow \dfrac {ord_p(2)} {2} \mid gcd (n,p-1)$ (discende da due note divisibilità)
Tornando al problema iniziale.
Si nota subito che $n=1$ è soluzione. Supponiamo ora $n\neq 1$
Abbiamo che $2^n\equiv -1 (n)$. Per TCR abbiamo $2^n \equiv -1 \pmod {p_i^{a_i}}$ per ogni $p_i^{a_i}$ che compare nella fattorizzazione di $n$
Quindi deve valere la tesi più debole $2^n \equiv -1 \pmod {p_i}$.
Sia $p_1$ il minor primo che compare nella fattorizzazione di $n$. Vale per quanto ottenuto sopra $2^{p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}}\equiv -1 \pmod {p_1}$
Per Fermat possiamo "cancellare" all'esponente di $n$ il fattore $p_1$, ottenendo $2^{p_2^{a_2}\dots p_k^{a_k}}\equiv -1 \pmod p_1$
Ma $\gcd (p_1^{a_1}\dots p_k^{a_k}, p_1-1)=1$, in quanto i fattori presenti in $p_1-1$ sono tutti minori degli altri primi per quanto detto su $p_1$.
Pertanto per il Lemma di Drago $\dfrac {ord_{p_1}(2)} {2}=1\Rightarrow ord_{p_1}(2)=2\Rightarrow p_1=3$
Per l'osservazione iniziale, l'esponente di $3$ è $1$
Sia ora $p_2$ il minor primo escluso il $3$ presente nella fattorizzazione di $n$. Con un ragionamento del tutto analogo al precedente otteniamo che
$\gcd (3\dots p_k^{a_k}, p_2-1)=1 \lor 3$, in quanto i fattori presenti in $p_2-1$ sono tutti minori degli altri primi escluso il $3$ per quanto detto su $p_2$.
Pertanto per il Lemma di Drago $\dfrac {ord_{p_2}(2)} {2}=1\Rightarrow ord_{p_2}(2)=2\Rightarrow p_2=3$ (assurdo perchè $p_2\neq 3$) oppure
$\dfrac {ord_{p_2}(2)} {2}=3\Rightarrow 8\equiv -1 \pmod {p_2}\Rightarrow p_2=3$ (assurdo)
Quindi non ci possono essere altri primi nella fattorizzazione di $n$ escluso $3$, che per quanto detto all'inizio compare solo con esponente 1.
Le uniche soluzioni quindi sono $n=1$, $n=3$
EDIT: forse ora è giusta
Infatti deve valere che $2v_3(n)\le v_3(2^n+1)=v_3(2+1)+v_3(n)$ , dove nell'ultimo passaggio abbiamo usato LTE.
Quindi svolgendo otteniamo $v_3(n)=1$ che è ciò vhe volevamo dimostrare.
La tesi implica che $n\mid 2^n+1$.
In prima battuta osserviamo che $(2,n)=1$ (altrimenti avremmo che un pari divide un dispari, assurdo). $2$ quindi non compare nella fattorizzazione di $n$
Enunciamo ora il Lemma di Drago: (me lo fece notare in forma quasi uguale in un problema di un annetto fa
)$a^n\equiv -1 (p) \Rightarrow \dfrac {ord_p(2)} {2} \mid gcd (n,p-1)$ (discende da due note divisibilità)
Tornando al problema iniziale.
Si nota subito che $n=1$ è soluzione. Supponiamo ora $n\neq 1$
Abbiamo che $2^n\equiv -1 (n)$. Per TCR abbiamo $2^n \equiv -1 \pmod {p_i^{a_i}}$ per ogni $p_i^{a_i}$ che compare nella fattorizzazione di $n$
Quindi deve valere la tesi più debole $2^n \equiv -1 \pmod {p_i}$.
Sia $p_1$ il minor primo che compare nella fattorizzazione di $n$. Vale per quanto ottenuto sopra $2^{p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}}\equiv -1 \pmod {p_1}$
Per Fermat possiamo "cancellare" all'esponente di $n$ il fattore $p_1$, ottenendo $2^{p_2^{a_2}\dots p_k^{a_k}}\equiv -1 \pmod p_1$
Ma $\gcd (p_1^{a_1}\dots p_k^{a_k}, p_1-1)=1$, in quanto i fattori presenti in $p_1-1$ sono tutti minori degli altri primi per quanto detto su $p_1$.
Pertanto per il Lemma di Drago $\dfrac {ord_{p_1}(2)} {2}=1\Rightarrow ord_{p_1}(2)=2\Rightarrow p_1=3$
Per l'osservazione iniziale, l'esponente di $3$ è $1$
Sia ora $p_2$ il minor primo escluso il $3$ presente nella fattorizzazione di $n$. Con un ragionamento del tutto analogo al precedente otteniamo che
$\gcd (3\dots p_k^{a_k}, p_2-1)=1 \lor 3$, in quanto i fattori presenti in $p_2-1$ sono tutti minori degli altri primi escluso il $3$ per quanto detto su $p_2$.
Pertanto per il Lemma di Drago $\dfrac {ord_{p_2}(2)} {2}=1\Rightarrow ord_{p_2}(2)=2\Rightarrow p_2=3$ (assurdo perchè $p_2\neq 3$) oppure
$\dfrac {ord_{p_2}(2)} {2}=3\Rightarrow 8\equiv -1 \pmod {p_2}\Rightarrow p_2=3$ (assurdo)
Quindi non ci possono essere altri primi nella fattorizzazione di $n$ escluso $3$, che per quanto detto all'inizio compare solo con esponente 1.
Le uniche soluzioni quindi sono $n=1$, $n=3$
EDIT: forse ora è giusta
"We' Inge!"
LTE4LYF
LTE4LYF