Is Euler's totient function a primitive recursive function?

Question

We consider the function $g$ which associates the number of prime integers with $n$ in the set $\{0,...,n\}$. I have to prove that $g$ is a primitive recursive function.

First I defined the set $A=\{i∈\{0,...,n\}:\gcd(i,n)=1\}$. To show that $A$ is a primitive recursive set I said that : $\{0,...,n\}$ is primitive recursive because ${k}$ is primitive recursive by characteristic function and $\{0,...,n\}=\bigcup\limits_{k=0}^{n} \{k\}$ is primitive recursive by the property of $⋃$.

Then the function $\gcd$ is primitive recursive. Indeed we can see that with the function $lcm$. We have $lcm(a,b)=μk≤ab (∃j,l≤ab,aj=k∧bl=k)$ which is a primitive recursive expression. Then by operator division $\gcd$ is a primitive recursive function.

So $A$ is a primitive recursive set.

Now, to prove that $g$ is primitive recursive can I take :

$g(i)=\sum\limits_{i=0}^{n} \chi_{A}(i)$ with $χ_A(i)=1$ if $i∈A$.and $g$ is a finite sum of primitive recursive functions so it is primitive recursive?

Answer 1

A computable function is primitive recursive if and only if it can be computed by a program whose running time is upper-bounded by some primitive recursive function. Your function (usually known as Euler's totient function $\varphi$) can be computed in exponential time, and so is primitive recursive.