1
$\begingroup$

I am trying to prove that $\phi(1)=1$ is the only case where $\phi (n)=n$

I can obviously discount all prime numbers due to the fact that $\phi(p) = (p-1)$

Whenever I try and prove the rest of the cases (for example, using $\phi(mn)=\phi(m)\phi(n)$), I keep falling into an endless loop of needing to prove that the only case where $\phi(n)=n$ only holds for 1.

$\endgroup$
  • $\begingroup$ For $n>1$, $\varphi(n)$ counts those elements between $1$ and $n-1$ which are relatively prime to $n$. Hence $\varphi(n)≤n-1$ (note that $n>1$ implies $\gcd(n,n)=n>1$). $\endgroup$ – lulu Apr 2 '17 at 0:05
  • $\begingroup$ @lulu $\varphi(n) = \# \{k \in \{1 \ldots n \}, gcd(k,n) = 1\}$. As you said $gcd(n,n) = n$ so $\varphi(n) \le n-1$ for $ n > 1$ $\endgroup$ – reuns Apr 2 '17 at 0:49
3
$\begingroup$

$1$ is the only number relatively prime to itself. Any other $n>1$ will have a maximum $n-1$ numbers from $1$ to $n$ itself that can be relatively prime to it, having to rule out at least $n$

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