How to find the number of distinct polynomial functions from $\mathbb{Z}_2$ to $\mathbb{Z}_2$? For any positive integer $n$, how many polynomials are there of degree $n$ over $\mathbb{Z}_2$? How many distinct polynomials function from $\mathbb{Z}_2$ to $\mathbb{Z}_2$?
Attempt: first part is clear to me since there are $2$ choices for each coefficient and there are $n$ coefficient so there are $2^n$ such polynomials. I am having problems understanding the second part where I need to find distinct polynomial functions.
If I assume $p(x)$ and $p'(x)$ are two equal polynomial functions over $\mathbb{Z}_2$ such that $p(x)=a_nx^n+\cdots+a_0$ and $p'(x)=a'_nx^n+\cdots+a'_0$, then $p'(x)=p(x)$ for $x=0,1$. So $a'_0=a_0$. And since the degree of these polynomials are $n$ then $a_n=a'_n=1$. So to find distinct polynomial functions we have to consider when $p(x)$ cannot be equal to $p'(x)$ for every value of $x\in\{0,1\}$. From here I cannot proceed. I was looking for solutions. Everywhere I see that they have started the argument with the fact that there are only $4$ such polynomials and then they give the examples of such polynomials. I need help to understand this problem. Thank you
 A: There are only 4 distinct functions $f: \Bbb Z_2 \to \Bbb Z_2$.
This is because the cardinality of the set of functions $A \to B$ is $$|B^A|=|B|^{|A|}$$
whenever $A,B$ are finite sets.
It happens that they are polynomial functions. Indeed they are
$$f_1(x)=0$$
$$f_2(x)=1$$
$$f_3(x)=x$$
$$f_4(x)=1-x$$
So we have found all of them.
A: Over $\Bbb{Z}_2$, the polynomial $x(x+1) = x^2 + x$ is identically $0$, which means I can replace $x^2$ with $x$ in any polynomial expression and get the same value. Using this repeatedly, over $\Bbb{Z}_2$, the polynomial $$a_0 + a_1 x + a_2 x^2 + ... + a_n x^n$$ always gives the same value as the polynomial $$a_0 + (a_1 + a_2 + a_3 + ... + a_n)x,$$ and so there are only $4$ distinguishable polynomials over $\Bbb{Z}_2$, depending on whether $a_0 = 0$ or $1$, and whether $a_1 + a_2 + a_3 + ... +a_n = 0$ or $1$.
A: The answer to your first question should be $2^{n-1}$ rather than $2^{n}$ since the coefficient of $x^n$ is always $1$.
For the second part note that the set of all polynomial functions is the set of all functions in your case.
EDIT: A pointed out in the comment the first part of this answer is incorrect.
