Mod 2 is primitive recursive Given a function E(x) which outputs 0 is x is even and 1 is x is odd, prove that this function is primitive recursive. 




My attempt is as follows

$$ E(x) = x \mod 2$$
To show that any function is primitive recursive, it must be obtained by composition and recursion from the initial functions $s(x) = x + 1; n(x) = 0$ and $u_i^n(x_1,x_2 \ldots x_n) = x_i$
We know that 
$$ E(0) = 0 $$
$$ E(x+1) = (E(x) + 1) \mod 2 $$
By using induction -
$$ E(n) = n \mod 2$$
Let $n = 0$
$$ E(0) = 0$$
which is easily shown to be primitive recursive since it is an initial function of the $PRC$ class.
Assuming that this is true for $n = k$.
$$E(k) = k \mod 2$$
Taking $ n = k+1 $
$$ E(k+1) = (E(k) + 1)\mod 2 $$

But at this point, I do not know how to proceed.
Define a function $a(x)$ by primitive recursion as follows: $a(0) = s(0)$ and $a(x+1) = 0$. In particular, this function satisfies $a(0) = 1$ and $a(1) = 0$. Now we can define $E(x)$ by primitive recursion: $E(0) = 0$ and $E(x+1) = a(E(x))$. You can prove that $E(x)$ works by induction (left to you).