Prove that if $t$ is a root of $f(x)$, then $t^2$ is a root of $f(x)$, where $f(x)=x^n+x^{n-1}+\cdots+x+1 \in \Bbb{Z}_2[x]$

Question

Suppose $f(x)=x^n+x^{n-1}+x^{n-2}+\cdots +x+1$ is a polynomial of degree $n$ defined over $\Bbb{Z}_2[x]$. When $a$, $b \in \Bbb{Z}_2$, we have $(a + b)^2 = a^2 + b^2$. This idea can be extended to any number of variables, that is, $(a_1+a_2+\cdots+a_r)^2=a_1^2+a_2^2+\cdots+a_r^2$, where $a_i \in \Bbb{2}$. Use this fact to help prove that if $t$ is a root of $f(x)$, then $t^2$ is a root of $f(x)$.

I understand that in $\mathbb{Z}_2$, the only elements are $0$ and $1$. $0^2=0$ and $1^2=1$. Is this all I need to prove that if $t$ is a root, so is $t^2$? Or am I missing something?

Answer 1

HINT:

The fact that $t$ is a root means that

$$ f(t)=t^n+t^{n-1}+\ldots t^2+t+1=0. $$

Over the given field you have that

$$ (a+b)^2=a^2+b^2 $$

which is extendable for more terms, so

$$ (a+b+c)^2=a^2+b^2+c^2 $$

and so on.

What happens when you take

$$ t^n+t^{n-1}+\ldots t^2+t+1=0 $$

and raise both sides to the power of $2$?

Compare it with $f(t^2)$.

Hope this helps, otherwise ask in the comments

Answer 2

Given a polynomial $f\in\mathbb{Z}_2[x]$ it doesn't have to have a root in $\mathbb{Z}_2$. An example would be $f=x^4+x+1$ or more applicable to your case $g=x^4+x^3+x^2+x+1$. You can check that just by plugging $0$ and $1$ into the equations: $$f(0)=0^4+0+1=1\ne0\text{ and } f(1)=1^4+1+1=3=1\ne 0$$ aswell as $$g(0)=1\text{ and } g(1)=1$$ What now? There's a theorem in algebra that says that for any polynomial $f$ of degree $n$ over some field $K$ there is a bigger field $L$ that contains $K$ such that $f$ splits into exactly $n$ linear factors. The smallest such field is called to splitting field of $f$ over $K$. But splitting into linear factors means we have zeros in this extension field of $K$. The standard example is $f=x^2+1$ over the field $\mathbb{R}$ where $f$ does not have roots! The extension field where $f$ splits turns out to be $\mathbb{C}$, i.e. $f=x^2+1=(x+i)(x-i)$, so we have the roots $i$ and $-i$ in the extension $\mathbb{C}$ of $f$ over $\mathbb{R}$.

As it turns out every field $L$ (not only a splitting field of some polynomial) containing the field $K$ has the same characteristic as $K$, so $\text{char}(L)=\text{char}(K)$.

So now turning to your problem: Given the polynomial $f=x^n+x^{n-1}+\dots+x+1$ in $\mathbb{Z}_2[x]$ there is a field $L$ containing $\mathbb{Z}_2$ such that $f$ has exactly $n$-roots in $L$. Your exercise is probably to show that given a root $t\in L$ then $t^2$ is also such a root (If your exercise restricts the variable purely to $\mathbb{Z}_2$ then the exercise would be trivial, as $t^2=t$ for either $0$ or $1$. So lets assume otherwise). We find that: \begin{align} f(t^2)&=(t^2)^n+(t^2)^{n-1}+\dots+(t^2)+1\\&=(t^n)^2+(t^{n-1})^2+\dots+t^2+1^2 \end{align} Notice that in the last line I replaced $1$ with $1^2$. As hinted at in your exercise we have that $(x+y)^2=x^2+y^2$ in $\mathbb{Z}_2$. This holds in any field of characteristic $2$ (we have the same effect with $(x+y)^p$ for a field of characteristic $p$ - this is called the Frobenius homomorphism if you are intersted) and as we said any field extension of $\mathbb{Z}_2$ also has characterstic $2$ so especially our splitting field $L$ and we can use the neat fact of Frobenius: \begin{align} f(t^2)&=(t^n)^2+(t^{n-1})^2+\dots+t^2+1^2\\&=(t^n+t^{n-1}+\dots+t+1)^2\\&=(f(t))^2\\&=0^2\\&=0 \end{align} so $t^2$ is a root of $f$ aswell!

Any question? I'll gladly answer :)