Exercise 2.7.1 (Reduce congruences to simpler equivalent congruences)

Question

Reduce the following congruences to equivalent congruences of degree $\leq 6$:
\begin{enumerate}
\item[(a)] $x^{11} + x ^8 + 5 \equiv 0 \pmod 7$;
\item[(b)] $x^{20} + x^{13} + x^7 + x \equiv 2 \pmod 7$;
\item[(c)] $x^{15} - x^{10} + 4x - 3 \equiv 0 \pmod 7$.
\end{enumerate}

Richard Ganaye · Accepted Answer

\begin{proof} 
\begin{enumerate}
\item[(a)] The Euclidean division by $x^7 - x$ gives modulo $7$
$$x^{11} + x ^8 + 5 \equiv (x^7 -x) \cdot (x^4 + x) + x^5 + x^2 + 5 \pmod {7}.$$

Therefore, for all integers $x$,
$$x^{11} + x ^8 + 5 \equiv 0 \pmod 7 \iff x^5 + x^2 + 5 \equiv 0 \pmod{7}.$$

With Sage
\begin{verbatim}
F7 = GF(7)
R.<x> = PolynomialRing(F7)
p = x^11 + x^8 + 5
s = x^7 - x
q,r = p.quo_rem(s); q,r
\end{verbatim}
$$\left(x^{4} + x,\ x^{5} + x^{2} + 5\right)$$

\item[(b)] Similarly,
$$x^{20} + x^{13} + x^7 + x -2 \equiv  (x^{13} + x^7 + x^6 + x + 2)(x^7  -x) + x^2 + 3x + 5 \pmod 7.$$
Therefore
$$x^{20} + x^{13} + x^7 + x \equiv 2 \pmod 7 \iff x^2 + 3x + 5 \equiv 0 \pmod 7.$$
\item[(c)] Finally, 
$$x^{15} - x^{10} + 4x - 3 \equiv  (x^8 + 6 x^3 + x^2)(x^7 - x) + 6 x^4 + x^3 + 4x + 4 \pmod 7.$$
So
$$x^{15} - x^{10} + 4x - 3 \equiv 0 \pmod 7 \iff  6x^4 + x^3 + 4x + 4 \equiv 0 \pmod 7.$$
\end{enumerate}
\end{proof}

Exercise 2.7.1 (Reduce congruences to simpler equivalent congruences)

Answers

Comments

Exercise 2.7.1 (Reduce congruences to simpler equivalent congruences)

Answers

Comments

Add answer