$n+1$ and $n \phi (n) + 1$ are both perfect squares if and only if $n$ is a product of twin primes?

Question

I'm trying to prove the following conjecture concerning twin primes and Euler's totient function, which I have verified for $n$ up to 1 billion.

For all $n \in \mathbb{N}$, $n+1$ and $n \phi (n) + 1$ are both perfect squares if and only if $n$ is a product of twin primes.

If is easy. Suppose $n = pq$ for primes $p$ and $q$ with $q=p+2$. Then

\begin{eqnarray} n+1 &=& pq + 1\\ &=& p(p+2) + 1\\ &=& (p+1)^2 \end{eqnarray}

and

\begin{eqnarray} n \phi (n) + 1 &=& pq(p-1)(q-1) + 1\\ &=& p(p+2)(p-1)(p+1) + 1\\ &=& p^4 + 2p^3 - p^2 - 2p + 1\\ &=& (p^2 + p -1)^2 \end{eqnarray}

I'm struggling with only if.

We know from $n = x^2 -1 = (x+1)(x-1)$ that $n$ must have a factor pair separated by 2. Based on the nature of the totient function I tried considering different cases based on the structure of the prime factorization.

In the case that $n$ is a semiprime we are done as the two factors must be twin primes, however, in the the case $n=pqr$, I get stuck. We have wlog that $pq = r +2$ and we need to show that

\begin{eqnarray} n \phi (n) + 1 &=& pqr(p-1)(q-1)(r-1) + 1\\ &=& pq(pq-2)(p-1)(q-1)(pq-3) + 1 \\ &=& p^{4}q^{4}-p^{4}q^{3}-p^{3}q^{4}-4p^{3}q^{3}+5p^{3}q^{2}+5p^{2}q^{3}+p^{2}q^{2}-6p^{2}q-6pq^{2}+6pq \end{eqnarray}

cannot be a square. I tried evaluating the expression modulo small primes but it didn't appear useful. Is there a better approach to solving this case?

Is there a better way to approach the conjecture in general?

Answer 1

COMMENT.- (don't put neither upvote nor downvote, please. This is not an answer but an equivalent reformulation of the problem that seems to me could be less dificult to try maybe).

Let $n\in \mathbb N$. One has $$\phi(n)=\frac{Y(Y+2)}{X(X+2)};\space \space Y,X\in\mathbb N\text { if and only if }n=pq\space \text{ where p,q are twin numbers. }\qquad (*)$$ The assertion could be false but to find a counterexample involves great numbers.

The difficult part is "only if"; for the "if" one has $\phi(n)=p^2-1=\dfrac{(p+p^2)(p^2+p-2)}{p^2+2p}$ where $X=p$ and $Y=p^2+p-2$. Remark however that this implies that also $\phi(n)$ must be of the form $Z(Z+2)$. Could be this useful for a proof of the hard "only if", in case the problem is true?

Answer 2

PARTIAL ANSWER: We wish to characterize solutions to $n\phi(n)=y^2-1$, given that $n=x^2-1$.

Basics: $n\ne 1$ because $2$ is not a square. $n$ is not a prime because the only prime $1$ less than a square is $3$, and $3\phi(3)+1=7$, not a square. $n$ is not a perfect power of an integer (including prime integers) because the only perfect power $1$ less than a square is $8$ (Mihailescu's theorem), and $8\phi(8)+1=33$, not a square. So $n$ is a composite number with at least two different prime factors.

$\phi(n)<n \Rightarrow n\phi(n)<n^2-1$. Let $n\phi(n)=(n-k)^2-1$, where $k<n$. $n\phi(n)=(n-k-1)(n-k+1)=(n-(k-1))(n-(k+1))$. Without deciding primality ahead of time, let us name $p=x-1, q=x+1$ so that $pq=x^2-1=n$. We can see that $q-p=2$ and $\gcd(p,q)\le 2$. Similarly, $(k+1)-(k-1)=2$ and $\gcd((k-1),(k+1))\le 2$.

$$\phi(n)=\frac{(n-(k-1))(n-(k+1))}{n}=\frac{(pq-(k-1))(pq-(k+1))}{pq}\\ \phi(pq)=\frac{(pq-(k-1))}{p}\frac{(pq-(k+1))}{q}=\left (q-\frac{(k-1)}{p}\right)\left(p-\frac{(k+1)}{q}\right)$$ The condition $k=x$ renders $\frac{(k-1)}{p}=1$ and $\frac{(k+1)}{q}=1$, leading to $$\phi(pq)=(p-1)(q-1)$$ which occurs only if $p,q \in \mathbb P$. Since $q-p=2$, they are twin primes.

The remaining gap in the proof is whether $k^2-1<n^2$, which has two factors that differ by $2$, can have two factors (prime or not) that differ by $2$ other than the known factors of $n$, $(x-1),(x+1)$. With the limitation on the magnitude of $k$, I don't think this is possible, but I have not found a proof of that yet. For odd $n$, i.e. even $k,x$, $\gcd((x-1),(x+1))=\gcd((k-1),(k+1))=1$, finding such other factors seems virtually impossible, but impressions are not a proof.