1
$\begingroup$

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?

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

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.