# For which integers $x$ does $\varphi(x)$ divide $3^x + 1$?

I'm working in a problem and I was wondering if there is a characterization of integers $x$ such that $\varphi(x)$ divides $3^x + 1$ . For primes $p$ this is equivalent to $p - 1$ divides $3^p + 1$ which means that every prime divisor $q$ of $p - 1$ we have $q - 1$ divides $2p$, but I can't find better.

Any suggestions?

• I have a hunch 1, 2, 3, 4, 5, 6, 22 are the only values of $x$ that work for this. – Robert Soupe Mar 1 '15 at 19:47

I can tackle the prime case easily enough. The required divisibility occurs if and only if $p=2,3$ or $5$. It is easy to check that these primes work.
Suppose $3^p + 1 \equiv 0 \bmod p-1$. Then $3^p \equiv -1 \bmod p-1$.
Now $\phi(p-1) < p$ and $p$ is prime so hcf$(\phi(p-1),p) = 1$.
Case $1$: suppose $\phi(p-1)>1$. Then we know by the above that $p$ is invertible mod $\phi(p-1)$. Raising both sides of the congruence to the inverse of $p \bmod \phi(p-1)$ tells us that $3 \equiv \pm 1 \bmod p-1$, hence $p-1$ divides $2$ or $4$ so that $p=2,3$ or $5$.
Case $2$: $\phi(p-1) = 1$. This happens if and only if $p=2$ or $p=3$.