3
$\begingroup$

For what values of n is $\phi(n)=n$ true? Just looking at tables of values it seems that $\phi(n)=n$ is true only for $n=0,1$ but I cannot come up with how to prove this.

I realize that the value of $\phi(0)$ is not really well-defined (What is the Euler Totient of Zero?) but for the purpose of this question I'll assume it is.

$\endgroup$
  • 1
    $\begingroup$ There is no reason even to define $\varphi(0)$. $\endgroup$ – André Nicolas Apr 30 '15 at 0:53
  • $\begingroup$ @AndréNicolas Whether there is a reason or not, Wolfram MathWorld says it's defined: $\phi(0)=1$. $\endgroup$ – user26486 Apr 30 '15 at 15:32
  • $\begingroup$ The opinion of Alpha is of interest, but more relevant are standard books. $\endgroup$ – André Nicolas Apr 30 '15 at 15:40
  • $\begingroup$ @AndréNicolas and yet WolframAlpha itself defines $\phi(0)=0$. It seems Wolfram is being inconsistent. $\endgroup$ – user26486 Apr 30 '15 at 16:29
  • $\begingroup$ For OP's question, what matters is the definition of $\varphi$ in the book/notes in which the question was asked. As to whether one should define $\varphi$ at $0$, the question really comes down to what do the standard books do? I believe that overwhelmingly they do not define $\varphi$ at $0$. However, that needs confirmation, which is not an easy task, since there are many elementary number theory texts, in many languages. $\endgroup$ – André Nicolas Apr 30 '15 at 16:47
6
$\begingroup$

First, $\varphi(n)$ is defined only for $n\ge 1$. Second, if $n=\prod\limits_{i=1}^r p_i^{r_i}$ for primes $p_1,\dots,p_r$, we have: $$\frac{\varphi(n)}n=\prod_{i=1}^r\Bigl(1-\frac1p_i\Bigr).$$ Thus, $\varphi(n)=n\iff\dfrac{\varphi(n)}n=1$ can be true if and only if $r=0$, i. e. $n=1$.

$\endgroup$
  • $\begingroup$ Wolfram MathWorld says that by convention $\phi(0)=1$, so it's not only defined for $n\ge 1$. $\endgroup$ – user26486 Apr 30 '15 at 15:24
  • 2
    $\begingroup$ That's pure convention. When I begun learning some number theory, it was defined for $n\ge 1$. $\endgroup$ – Bernard Apr 30 '15 at 15:26
5
$\begingroup$

From the definition of $\phi(n)$ is the number of positive integers not exceeding $n$, that are relatively prime to $n$. Further, for $n>1$, we have $\gcd(n,n) = n$. Hence, for $n > 1$, we have $\phi(n) < n$. Hence, $n$ can be only $0$ or $1$.

$\endgroup$
  • $\begingroup$ $\phi(0)=1$ (see Wolfram MathWorld). $\endgroup$ – user26486 Apr 30 '15 at 15:33
  • 2
    $\begingroup$ @user26486 This can be argued, and Wolfram Alpha saying so does not settle the issue. $\endgroup$ – Robert Soupe Jul 8 '15 at 1:35
  • $\begingroup$ Oops, that says Mathworld, not Alpha. Note also that it says "the Wolfram Language defines EulerPhi[0] equal to 0 for consistency with its FactorInteger[0] command." $\endgroup$ – Robert Soupe Jul 8 '15 at 1:37
  • $\begingroup$ A convention accepted by the mathematical community always has a motivation. By the way, $0!=1$ is also a convention. $\endgroup$ – Piquito Jul 8 '15 at 2:14
  • $\begingroup$ @Ataulfo Yes, but $0! = 1$ is a useful convention and accepted by the mathematical community. $\varphi(0) = 1$ or $\varphi(0) = 0$ or $\varphi(0) = 2$ are not standard conventions and are not accepted by the mathematical community $\endgroup$ – 6005 Aug 26 '15 at 15:42
2
$\begingroup$

yes what you said is true $\phi(n) = n$ if and only if $n=0,1$

Now actually $\phi(n) \leq n-1$ for all $n \geq 2$ and $\phi(n) = n-1$ only occurs when $n$ is prime at this case

$\endgroup$
  • $\begingroup$ MathWorld says $\phi(0)=1\neq 0$. $\endgroup$ – user26486 Apr 30 '15 at 16:27
1
$\begingroup$

Here you have another proof: For $n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$ with $p_i$ prime numbers, $\phi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\dots(1-\frac{1}{p_k}) < n$ as $0<1-\frac{1}{p_i}< 1\ \forall p_i$.

$\endgroup$
  • $\begingroup$ I've given (almost) the same answer! ;o) $\endgroup$ – Bernard Apr 30 '15 at 1:00
  • $\begingroup$ Oh yes :) TLTR ( too late to read :D) $\endgroup$ – Alvaro Fuentes Apr 30 '15 at 1:10
  • $\begingroup$ @Bernard But you unpacked it more. $\endgroup$ – Robert Soupe Jul 8 '15 at 1:39
0
$\begingroup$

$\varphi(n)$ is the number of integers $k$, $1 \le k \le n$, relatively prime to $n$. This gives us immediately that $\varphi(n) \le n$ for all $n$.

But for $n \ge 2$, $n$ is not relatively prime to itself, so we have that $\varphi(n)$ is equivalent to the number of integers $k$, $1 \le k \le n-1$, relatively prime to $n$. Thus $\varphi(n) \le n-1$ for $n \ge 2$. In particular, the only solution to $\varphi(n) = n$ is $n = 1$. ($\varphi(0)$ is not usually defined.)

$\endgroup$
-1
$\begingroup$

By definition, $\phi(n)<n$ for $n\ge 2$ since, $(n,n)=n$.

$\endgroup$
  • $\begingroup$ Why the downvotes?! This is perfectly correct. $\endgroup$ – 6005 Aug 26 '15 at 15:43

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.