On a previous Cryptography exam I'm working through, there is the following problem:
Given $$f(x) = x^{134}+x^{127}+x^{7}+1$$ and the field $\mathbb{F}_{2^{n}}$ where $n=1463$, how many roots does the polynomial have? The polynomial has the form $f(x) = (x^{7}+1)(x^{127}+1)$, this is clear. It's also clear that the order of the field is $2^{1463}-1$. At this point I was unsure how to continue, so I peaked in the solution from that year's exam, and I was very confused by their arguments. This is how they solved it:
The order of the multiplicative group is $2^{1463}-1$, and $2^{1463}-1 \equiv 3 \bmod{7}$, and hence $x^{7}+1$ has only the one root, $1$. I've tried working out why this must be the case, but can't do it. Would be glad if someone could explain. Furthermore, $2^{1463} \equiv 1 \bmod{127}$, so $127$ divides the order of the group, so there are $127$ solutions in the field to the full polynomial when the zeros are counted without multiplicity, and $128$ when counted with multiplicity.
I would be very glad if someone could try to explain the reasoning presented in the solution.
Cauchy's theorem states that if a prime $p$ divides the order of a group, then that group has an element of order $p$. In fact, this goes both ways, since an element of order $p$ generates a subgroup of order $p$, and the order of the subgroup must divide the order of the group it is in.
$\mathbb{F}_{2^n}$ is a group under multiplication. $2^{1463}-1 \equiv 3 \bmod{7}$ implies that $7$ does not divide the order of the group, and therefore there is no element $g \in \mathbb{F}_{2^n}$ such that $g^7 = 1$ except for $g=1$.
If there were nontrivial elements satisfying this, then taking the additive inverse $-g$, we find that this is a root of $x^7+1$, since $(-g)^7 + 1 = (-1)^7g^7+1 = (-1)(1) + 1 = 0$.
Because $2^{1463} \equiv 1 \bmod{127}$, $127$ divides the order of $\mathbb{F}_{2^n}$, and therefore since $127$ is also prime, there exists an element of order $127$. If we look at the subgroup generated by this element, we will find that actually every element of this subgroup has order $127$, so any of these satisfies the equation $g^{127} = 1$. Therefore, if we take $-g$, $(-g)^{127}+1 = 0$ as above, and we have at least $127$ solutions to the polynomial $x^{127}+1$.
I say "at least", because this doesn't actually prove that there are exactly $127$ elements of order $127$. It is not clear to me why there could not be more.