According to wikipedia, definition of Euler's totient function (or Euler's totient function) is:

Euler's totient function is an arithmetic function that counts the positive integers less than or equal to $n$ that are relatively prime to $n$, ie if $n$ is a positive integer, then $\phi(n)$ is the number of integers $k$ in the range $1 ≤ k ≤ n$ for which the greatest common divisor $gcd(n, k) = 1$.

Why does the definition specifically mention that the relative prime number to $n$ can be equal to $n$ (Check the highlighted area in the definition)?

I think that for any positive number $n$ the value of $gcd(n,n)$ will always be $n$, so $n$ is never relatively prime to $n$. So why does it state that range of $k$ is $1 ≤ k ≤ n$ instead of $1 ≤ k < n$

Am I correct in making this assumption? Is there any exception?

  • 1
    $\begingroup$ Exception is $n=1$. I would use the number between $0$ and $n-1$ that are relatively prime to $n$. Same function. $\endgroup$ – André Nicolas May 14 '15 at 16:28

We want $\phi(1)=1$ cause that makes $\phi$ multiplicative.


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.