9
$\begingroup$

I did the following proof and I was wondering if its valid. It feels wrong because I didn't actually test the case when purportedly $n$ is not prime, but please feel free to correct me.

Assume there exists $n$ such that $\phi(n) = 14$. Assume $n$ is prime. Then $\phi(n) = n-1$. Then here, n-1 = 14, so n = 15. We know since Euler's totient function is multiplicative that $\phi(xy)$ = $\phi(x)\phi(y)$, so $\phi(15) = \phi(3)\phi(5)$, but alas $\phi(3)\phi(5) = 2\cdot4 = 8 \ne 14$. If $n$ is not prime a similar argument follows since we know then that $n$ must be composed of prime numbers by the prime factorization theorem.

$\endgroup$
  • 1
    $\begingroup$ I don't see at all what "similar argument" you're implying for the case when $n$ isn't prime, could you explain? $\endgroup$ – Jack M Apr 14 '14 at 23:05
  • 2
    $\begingroup$ (Also, your argument for the prime case is a bit complicated. Assume $n$ is prime, then $n=15$, contradiction!). $\endgroup$ – Jack M Apr 14 '14 at 23:09
17
$\begingroup$

If a prime $p\mid n$, then $p-1\mid\phi(n)$. If $\phi(n)=14$, then, since the divisors of $14$ are $\{1,2,7,14\}$, $p\in\{2,3\}$. Thus, $n=2^a3^b$ and $\phi(n)$ is of the form $2^j3^k$. However, there is no factor of $7$ in $2^j3^k$.

$\endgroup$
  • $\begingroup$ Where is the 3 coming from? $\endgroup$ – Arthur Collé Apr 14 '14 at 23:12
  • $\begingroup$ @ArthurCollé: the set of divisors of $\phi(n)$ is $\{1,2,7,14\}$, therefore, the possible set of primes that divide $n$ is $\{2,3,8,15\}$, which can be reduced to $\{2,3\}$ since neither $8$ nor $15$ are primes. $\endgroup$ – robjohn Apr 14 '14 at 23:16
  • $\begingroup$ Thanks. I see how $n = 2^a 3^b$ but then why is $\phi(n) = 2^a 3^{b-1}$? What equality establishes that relationship? $\endgroup$ – Arthur Collé Apr 14 '14 at 23:20
  • $\begingroup$ @ArthurCollé: if $n=\prod\limits_ip_i^{e_i}$, where $p_i$ is prime and $e_i\gt0$, then $\phi(n)=\prod\limits_i(p_i-1)p_i^{e_i-1}$. $\endgroup$ – robjohn Apr 14 '14 at 23:25
7
$\begingroup$

We answer the question, but in a way that is far too convoluted for the particular numerical example of the post. We prove the following result.

Lemma: If $\varphi(n)=2q$, where $q$ is an odd prime, then $2q+1$ is prime.

An immediate consequence is that we cannot have $\varphi(n)=14$. For then $q=7$, but $2q+1$ is not prime.

We now prove the lemma. Suppose that $\varphi(n)=2q$. We divide the analysis into cases.

Case $1$: Maybe $n=2^km$, where $k\ge 3$ and $m$ is odd. Then by the multiplicativity oof $\varphi$, we have $\varphi(n)=\varphi(2^k)\varphi(m)$. This is impossible, since $\varphi(2^k)=2^{k-1}$, which is divisible by $4$. But $2q$ is not divisible by $4$.

Case $2$: Maybe $n=4m$, where $m$ is odd. Then $\varphi(n)=2\varphi(m)$. Since $2q$ is twice an odd number, it follows that $\varphi(m)$ is odd. This is only possible for an odd number $m$ if $m=1$. But then $\varphi(m)=2\ne 2q$.

Case $3$: Maybe $n=2m$ or $n=m$, where $m$ is an odd number. In either case, $\varphi(n)=\varphi(m)$.

Suppose that $m$ can be factored as a product $st$, where $s$ and $t$ are relatively prime, and neither $s$ nor $t$ is equal to $1$. Then $\varphi(s)$ and $\varphi(t)$ are each even, so $\varphi(m)$ is divisible by $4$. But $2q$ isn't, so we cannot have $\varphi(m)=2q$.

It remains to deal with the case where $m$ is a prime power, perhaps equal to $1$. If $m=1$, then $2q=2$, not twice an odd prime.

Now suppose that $m=p^k$, where $p$ is an odd prime, and $k\ge 1$. Then $\varphi(m)=p^{k-1}(p-1)$. This can be twice an odd prime in $2$ ways: (i) $k=1$ and $p-1$ is twice an odd prime, or (ii) $p=3$ and $k=2$.

In Case (i), $2q=p-1$, so $2q+1$ is prime. In Case (ii), $2q=6$, so again $2q+1$ is prime.

$\endgroup$
  • $\begingroup$ In the second last paragraph of your solution, there's a problem, exactly with (i). $\endgroup$ – user98186 Feb 29 '16 at 23:16
  • $\begingroup$ @NimaBavari: Thank you, fixed I think, I had left out the crucial word "twice." $\endgroup$ – André Nicolas Feb 29 '16 at 23:25
  • $\begingroup$ You're welcome. (+1) for thorough solution. $\endgroup$ – user98186 Feb 29 '16 at 23:28
-1
$\begingroup$

This does not hold. What kind of similar argument are you then talking about?

You can use the fact that $\phi$ is multiplicative. Assume $n = p_1^{a_1}p_2^{a_2}...p_t^{a_t}$, then $\phi(p_1^{a_1}p_2^{a_2}...p_t^{a_t})$ $\phi(p_1^{a_1})\phi(p_2^{a_2})...\phi(p_t^{a_t}) = 2 \cdot 7 = 1 \cdot 14$

Use this to arrive at a contradiction.

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