TITLE: Build all polynomial functions over field $\mathbb{Z}_{k}$
QUESTION [2 upvotes]: Consider two functions $[x^{2}y, x+1]$ and $\mathbb{Z}_{k}$, where $k$ is a prime number.
Is it true that we could build all polynomial functions $P(x)$ over this field using composition of these functions? We should find all $a_{k-2}x^{k-2} + \dots+a_{1}x^{1} + a_{0}$, where $a_{i} \in \mathbb{Z}_{k}$. And composition means: we can build the identity function $x$, and if we have built $f(x)$ and $g(x)$, we can also build $f^2(x)g(x)$, $f(x) + 1$.
EDIT : $x^{k-1+l} \equiv x^{l}$. So we just need to build $x^{m}$, where $ 0 \le m < k - 1$.
My attempt : 
Obviously we can build all $x^{2m+1}$ and even $x^{2m+1} + l \cdot x^{2m}$, where $0 \le l < k$. But I got stuck on how can I get all monomials with even degree. If I built them it's easy to struct all constants , or if I build all constant it will be easy to struct all even-degree monomials (because of Fermat's theorem). But I don't know what to do in this way? 
EDIT : we could use Fermat's theorem.
Any ideas?

REPLY [1 votes]: Yes, it is true.  Let us first assume $k$ is odd.  Note that if we can build a function $f(x)$, then for any $a,b\in\mathbb{Z}_k$ we can also build the function $$g(x)=(x-a)^{k-1}(f(x)-b)+b.$$ Indeed, to build this function we first add $1$ (the residue of) $-b$ times to get $f(x)-b$.  Then since we can build $x-a$, we can multiply by $(x-a)^2$ $(k-1)/2$ times (here we use that $k$ is odd).  Finally, we can add $1$ $b$ times to get $g(x)$.
Now note that if $x\neq a$, $(x-a)^{k-1}=1$ so $g(x)=f(x)$.  On the other hand, $g(a)=b$.  So this means that we can freely modify the value of $f(x)$ at one point at a time.  Repeatedly using this as $a$ ranges over all elements of $\mathbb{Z}_k$ allows us to construct any function at all.
This proves the result when $k$ is odd.  When $k=2$, the only functions we need to build are $0$, $1$, $x$, and $x+1$.  We can obviously build $x$ and $x+1$, and we can build $0$ as $x^2(x+1)$ and thus we can also build $1$.  So the result is true for all primes $k$.
{"set_name": "stack_exchange", "score": 2, "question_id": 2210565}