Calculating $\phi(63)$

Question

For the Euler phi function, if $\gcd(m, n) = 1$, then $\phi(mn) = \phi(m) \phi(n)$. So why is $\phi(63)=\phi(7)\phi(9)=6\cdot8=48$ wrong?

Answer 1

You should note that $$\phi(x)=x(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_n})$$where $p_1,p_2,\cdots,p_n$ are prime divisors of $x$ and are not repeated .

It means if $x=p_1^3$ then $\phi(x)=x(1-\frac{1}{p_1})$ and not $\phi(x)=x(1-\frac{1}{p_1^3})$

Plug in $63$ in place of $x$ and you will get$$\phi(63)=63(1-\frac{1}{7})(1-\frac{1}{3})$$$$\phi(63)=36$$

or$$\phi(63)=\phi(7)\phi(9)$$$$\phi(63)=7(1-\frac{1}{7})\times9(1-\frac{1}{3})$$$$\phi(63)=36$$

Answer 2

You should note that $\phi(9)=6$, because it's not a prime number.

Answer 3

The function satisfies for prime $p$ and $k \geq 1$ that $\phi(p^{k}) = p^k - p^{k-1}$. Hence $\phi(9) = \phi(3^2) = 3^2 - 3^1 = 6$. So you should calculate $\phi(63) = 6 \cdot 6 = 36$.

You can easily understand this property from the definition of $\phi$. Note that $\phi(n)$ is the number of positive integers less than $n$ which are relatively prime to $n$. Consider prime $p$ and positive $k.$ Then the only positive integers not relatively prime to $p^k$ are those which are divisible by $p.$ There are precisely $\frac{p^{k}}{p} = p^{k-1}$ such numbers less than or equal to $p^k.$ Hence there are $p^k - p^{k-1}$ positive integers relatively prime to $p^k$ and less than it.

Answer 4

The definition of Euler's totient function is that $\phi(k)$ is the number of integers $N$ such that $1\leq N \leq K$ and $\gcd(K,N) = 1$. In short, it is the number of totatives of $n$.

The totatives of $9$ are $S =\{1,2,4,5,7,8\}$, because they are all smaller or equal to $9$ and they are all coprime to it. $3,6,9$ all have the $\gcd$ with $9$ different than $1$. Thus, $\phi(9) = |S|\implies \phi(9) = 6$.

Take note that there is a formula for the case $k$ is a power of a prime number. That is $\phi(k) = \phi(x^n) = x^n - x^{n-1}$. Thus, for $9$, you get:

$$\phi(9) = \phi(3^2) = 3^2 - 3^{2-1} = 9 - 3^1 = 6$$