Dio$\phi$antea

[Parmenide]

Trovare tutte le coppie di interi positivi $m,n$ tali che

$$ 2^n+(n-\phi(n)-1)!=n^m+1 $$

[TeoricodeiNumeri]

Propongo la mia soluzione nella speranza che sia corretta (mi scuso in anticipo per il fatto che è lunga: probabilmente si può accorciare).[math]

Testo nascosto:

Vogliamo dimostrare che le uniche soluzioni sono $(2;2)$ e $(4;2)$.
Come prima cosa verifichiamo che queste due sono soluzioni. Difatti $2^2 +(2-1-1)!=2^2 +1$ e similmente $2^4 +(4-2-1)!=4^2 +1$.
Dimostriamo ora che non ce ne sono altre.
Verifichiamo innanzitutto che non ci sono altre soluzioni con $n$ pari. Difatti per $n\geq 6$ abbiamo che $\phi(n)\leq \frac{n}{2}$ da cui $n-\phi(n)-1\geq \frac{n}{2}-1>1$. Di conseguenza il primo membro dell'equazione è pari mentre il secondo è dispari.
Supponiamo ora $n$ dispari. Dimostriamo che se $n\mid (n-\phi(n)-1)!$ allora non ci sono soluzioni. Difatti $n$ non può essere $1$ (altrimenti al primo membro comparirebbe $(-1)!$), per cui non è riduttivo supporre che $n=\prod_{i=1}^{k} p_{i}^{\alpha _i}$ con tutti i $p_i$ primi distinti e $p_1<p_2<\dots<p_k$ e gli $\alpha_i$ non nulli. Di conseguenza abbiamo che $2^{n}\equiv 1 (\mod p_1)$. Di conseguenza detto $d$ il massimo comun divisore fra $n$ e $p_1 -1$ abbiamo che $2^d \equiv 1(\mod p_1)$. Ma tutti i fattori primi di $n$ sono maggiori di $p_1 -1$ da cui $d=1$ e quindi $2\equiv 1 (\mod p_1)$ da cui $p_1 \mid 1$ ma $p_1$ è un primo (e di conseguenza non divide $1$). Di conseguenza $n$ non può dividere $(n-\phi(n) -1)!$.
Supponiamo nuovamente che $n=\prod_{i=1}^{k} p_{i}^{\alpha _i}$ con i $p_i$ tutti primi, gli $\alpha_i$ non nulli e questa volta $p_1^{\alpha_1}<p_2^{\alpha_2}<\dots<p_k^{\alpha_k}$ e dimostriamo che se $k\geq 2$ allora $n \mid (n-\phi(n)-1)!$, e in particolare dimostriamo un'asserzione più forte, ovvero che $n-\phi(n)-1\geq p_k^{\alpha_k}$.
Per $k=2$ abbiamo che $n-\phi(n)-1=p_1^{\alpha_1 -1}\cdot p_2^{\alpha_2 -1}(p_1+p_2 -1)-1 \geq p_2^{\alpha_2}$. Supponiamo ora che la proprietà valga per un $k$ qualsiasi e dimostriamola per $k+1$. Difatti abbiamo che $n-\phi(n)-1=\prod_{i=1}^{k+1} p_{i}^{\alpha _i-1}[\prod_{i=1}^{k+1} p_{i} -\prod_{i=1}^{k+1} (p_{i}-1)]-1>(\prod_{i=1}^{k+1} p_{i}^{\alpha _i-1})(p_1 -1)[\prod_{i=2}^{k+1} p_{i} -\prod_{i=2}^{k+1} (p_{i}-1)]-1\geq^{ip. \hspace{1mm} ind.}\\(\prod_{i=1}^{k+1} p_{i}^{\alpha _i-1})(p_1-1)\cdot (p_{k+1}+1) -1\geq p_{k+1}^{\alpha _k+1} $
Di conseguenza esiste un primo $p$ dispari e un intero positivo $a$ per cui $n=p^a$.
Se $a=1$ abbiamo che $2^p +0!=p^m +1$ da cui $p=2$ ma $p$ è dispari. Se $a=2$ allora abbiamo che $(p^2)^m +1\equiv 2(\mod 8 )$ che implica che $2 \mid \mid (p^2)^m +1$, da cui $p=3$ perché altrimenti $(n-\phi(n)-1)!=(p-1)!$ sarebbe divisibile per $4$ e lo stesso si potrebbe dire di $2^{(p^2)}$. Ma per $p=3$ si avrebbe $2^9 +2=9^{m}+1$ che non ha soluzioni intere positive in $m$. Similmente per $a=3$ si ha che $(p-3)p(p-2)p(p-1)p$ e in particolare $n$ divide $(n-\phi(n)-1)!=(p^2-1)!$ tranne per $p=3$ che di nuovo non produce soluzioni. Infine se $a\geq4$ notiamo che $p^{a-3}(p-2)p^{a-2}(p-1)p^{a-2}$ divide $(n-\phi(n)-1)!$ con $a-3+a-2+a-2>a$ e quindi $n\mid (n-\phi(n)-1)!$. Di conseguenza se $n$ è dispari non ci sono soluzioni c.v.d.