4
$\begingroup$

I know of different types of solutions to relations between$\varphi(n)$ and$n$, e.g. the classical question to find all positive integers$n$ for which$\phi(n)$ divides$n$. But the following eludes me.

For which positive integers$n$ do we have$3 \varphi(n) = n+1$?

A search for$n<10^9$ turns up only the solution$n=2$. But I have no proof that$n=2$ is the only solution. It is not too hard to come up with the conclusion that a solution$n>2$ can have only prime factors at least$5$ and that$n$ is square free. Moreover, potential solutions need to have quite some number of prime factors. But I did not get anything much beyond that, despite the feeling that an elementary number theoretic proof should be possible (if the claim is correct).

Update: As an answer (which, unfortunately, was incorrect) was deleted, also the comments to that answer were deleted. There was some interesting reasoning there going as follows: If$n>2$, then$n$ has to be square free and is not divisible by 2 or 3, so that the equation turns into$$ 3 \prod_{i=1}^k \left( 1-\frac{1}{p_i} \right) = 1 + \frac{1}{n},$$ where$p_1,\dots,p_k$ are the different prime factors of$n$. Then, letting$q_1,\dots,q_k$ be the first$k$ primes starting with$q_1=5$, if$$ 3 \prod_{i=1}^k \left( 1-\frac{1}{q_i} \right) > 1 + \frac{1}{q_1 \dots q_k},$$ then no solution with$k$ prime factors can exist. This gives a lower bound$k=33$ and therefore a rather large lower bound on possible solutions$n > 10^{56}$, which is$\infty$ for all practical purposes, but does not answer the question.

askedOct 4 at 13:47
pi in the sky's user avatar
$\endgroup$
6
  • 1
    $\begingroup$What is the source of this problem? It makes a difference. If, say, this is a homework problem then one would imagine that it has a sensible solution. If it is a phenomenon you have noticed, then of course it might be true but very hard to prove. Of course, a search should be done to rule out modest sized counterexamples.$\endgroup$CommentedOct 4 at 13:50
  • 1
    $\begingroup$It's a question I came up with studying related questions like the one mentioned in the post. I did a search for solutions $n<10^9$. A general type of question would be to find, given integers $a,b,c$, all solutions to $a\varphi(n) + b n + c = 0$. Easy ones are $\varphi(n)=n-1$ giving all the primes as solutions or $2 \varphi(n)= n$ giving all the powers of 2. A more difficult and interesting one is $4 \phi(n) = n+2$ where there are finitely many solutions. I have the feeling that the above is a typical not so easy, but doable one. But who knows.$\endgroup$CommentedOct 4 at 14:09
  • 2
    $\begingroup$I suggest editing your post to include all that information. Don't leave it for the comments.$\endgroup$CommentedOct 4 at 14:10
  • $\begingroup$I included the brute force search limit in the post. I think the remaining information is well situated in the comments.$\endgroup$CommentedOct 4 at 14:16
  • 1
    $\begingroup$A solution must be of the type $3k+2$ and in general these numbers ($ap+q, a\ge 0$ with $q$ not a quadratic residue mod $p$ prime) are harder to understand$\endgroup$CommentedOct 4 at 14:18

0

You mustlog in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.