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?

  • 2
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – Raphael
    Jun 17, 2016 at 20:12
  • $\begingroup$ @Raphael Ok I will try to modify $\endgroup$
    – Maman
    Jun 17, 2016 at 22:20

1 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.

  • $\begingroup$ Really nice and fast ! Impressive. I think my answer is more technical $\endgroup$
    – Maman
    Jun 17, 2016 at 22:16
  • $\begingroup$ @Maman For the purpose of exercise hand-ins, note that you'll have to have either a theorem for this upper-bounding fact, or need to prove that. As far as I can tell, it's not at all trivial. $\endgroup$
    – Raphael
    Jun 18, 2016 at 9:37
  • 3
    $\begingroup$ I do not think this is correct reasoning. See this question with Joel's and Jason's answers to it. If the running time of a Turing machine computing the function is bounded by a primitive recursive function, the function is primitive recursive, but not necessarily if just the range of the function is bounded by a primitive recursive function. $\endgroup$
    – Deadcode
    Mar 26, 2021 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.