# Polynomial Modulus

So I am studying for finals and I came across this problem and I am completely stuck. I would really appreciate someone to clarify on the steps to take to solve these problems.

Let $f(x) = x^4 + x^3 + 1$ , which is an element of $\mathbb Z_2[x]$

a.) Show that $x^{16}\equiv x\pmod{f(x)}$

b.) What is the smallest integer $k>0$, so that $x^k\equiv 1\pmod{f(x)}$

• Note that $x^4 \equiv x^3+1 \pmod{f(x)}$, and work from there: $x^5 = x^4\times x = \cdots$, etc. – fkraiem Dec 9 '14 at 20:19
• fkraiem's hint is good, but this is really more of a math problem than a cryptography problem. – Guut Boy Dec 9 '14 at 20:20
• Hint: for a.) the first steps are: $x^{16}=x^{12}(x^4+x^3+1)+x^{15}+x^{12}$, therefore $x^{16}\equiv x^{15}+x^{12}\pmod{f(x)}$; $\;$ $x^{15}+x^{12}=x^{11}(x^4+x^3+1)+x^{14}+x^{12}+x^{11}$, therefore $x^{16}\equiv x^{14}+x^{12}+x^{11}\pmod{f(x)}$. – fgrieu Dec 9 '14 at 20:25
• Awesome! got a now any idea how to do pt b? – ABC Dec 9 '14 at 21:03

Note that $f$ is irreducible over $\mathbb F_2$, which you can easily show using the observation that if it was reducible, there was a non-trivial divisor of degree $1$ or $2$, and disproving both of these possibilities by trial division. Therefore, $\mathbb Z_2[x]/(f)$ forms a field isomorphic to $\mathbb F_{2^{\deg f}}=\mathbb F_{16}$.
1. Since the non-zero elements of $\mathbb F_{16}$ form a (multiplicative) group of order $15$, by Fermat's little theorem, one has $a^{15}=1$ for all $a\in\mathbb F_{16}$. Therefore, $x^{16}+(f)=(x+(f))^{16}=x+(f)$, implying $x^{16}\equiv x\mod f$.
2. Note that by Lagrange's theorem, $k$ must divide said group's order $15$. The only possible values smaller than $15$ are therefore $1$, $3$ and $5$, all of which one can easily eliminate by calculation:
• $(x+(f))^1=x+(f)\neq1+(f)$;
• $(x+(f))^3=x^3+(f)\neq1+(f)$;
• $(x+(f))^5=x^3+x+1+(f)\neq1+(f)$.
Hence, $k=15$ is the smallest exponent such that $x^k\equiv1\mod f$.