# Question regarding solving polynomial of congruence?

In my textbook, they said:

$$2x^{3} + 7x - 4 \equiv 0 \pmod{5}$$

The solution of this equation are the integers with $x \equiv 1 \pmod{5}$, as can be seen by testing $x = 0, 1, 2, 3,$ and $4.$

And I have no clue how do they had $x \equiv 1 \pmod{5}$. I tested as they suggested:

Let $y = 2x^{3} + 7x - 4$, we have:
$$x = 0: y = -4, \implies y \equiv 1 \pmod{5}$$ $$x = 1: y = 5, \implies y \equiv 0 \pmod{5}$$ $$x = 2: y = 26, \implies y \equiv 1 \pmod{5}$$ $$x = 3: y = 71, \implies y \equiv 1 \pmod{5}$$ $$x = 4: y = 152, \implies y \equiv 2 \pmod{5}$$

What I did not understand is how these five modulo equations become $x \equiv 1 \pmod{5}$? Can anyone help me explain this?

Thanks,

-

Any integer is going to be congruent to one of $0,1,2,3,4$ modulo $5$. As the testing shows, only those integers which are congruent to $1$ modulo $5$ are solutions, and any integer congruent to $1$ mod $5$ is a solution.

Those tests are using an arbitrary $x$ each time, so you shouldn't think of them as a system of congruences of a single variable $x$ but instead they imply the result described above.

Here's another thing to add which may help. Don't just check $0,1,2,3,4$. Take $x$ to be any arbitrary integer, not necessarily one of those just listed. So like I said before, this arbitrary $x$ is congruent to one of $0,1,2,3,4$ since they form a complete residue system. If $x\equiv 0\pmod{5}$, then $$2x^3+7x-4\equiv 2(0)^3+7(0)-4\equiv -4\equiv 1\pmod{5}$$ so $x$ is not a solution. Likewise if $x\equiv 2,3,4\pmod{5}$. So the only choice which works is when $x\equiv 1\pmod{5}$. Hopefully that's clearer?

-
Thanks. But how do they get that equation, I'm still confused :(. – Chan Mar 10 '11 at 7:13
@Chan, what equation do you mean? – yunone Mar 10 '11 at 7:14
Oh, I meant $x \equiv 1 \pmod{5}$. Thank you. – Chan Mar 10 '11 at 7:20
Yes, it was much clearer now. Thank you. – Chan Mar 10 '11 at 7:23
@Chan, ok, good to hear. – yunone Mar 10 '11 at 7:23

What your textbook means is $$\left(2x^{3} + 7x - 4 \equiv 0 \pmod{5} \right) \iff \left(x \equiv 1 \pmod{5} \right)$$

This is what you checked by plugging in the different cases for $x$.

By taking $x \equiv 1 \pmod{5}$, you proved that $2x^{3} + 7x - 4 \equiv 0 \pmod{5}$ and hence $$\left(x \equiv 1 \pmod{5} \right) \Rightarrow \left(2x^{3} + 7x - 4 \equiv 0 \pmod{5} \right)$$

Now by taking $x \neq 1 \pmod{5}$, you proved that $2x^{3} + 7x - 4 \neq 0 \pmod{5}$ and hence $$\left(2x^{3} + 7x - 4 \equiv 0 \pmod{5} \right) \Rightarrow \left(x \equiv 1 \pmod{5} \right)$$

-
Ambikasaran: I still can't see it. For an arbitrary polynomial how can we tell? Is the book guessing? Thanks. – Chan Mar 10 '11 at 7:12

\begin{aligned} 2x^3+7x-4 \equiv 0 ( mod 5)\\ 2x^3+2x-4 \equiv 0 ( mod 5)\\ 2(x-1)(x^2+x+2) \equiv 0 ( mod 5) \end{aligned}

Now you have two solutions $x-1 \equiv 0 (mod5)$ or $x^2+x+2 \equiv 0 (mod5)$. You can continue and verify if $x \equiv 1 ( mod 5)$ is the only solution.

-
Thank you. I see it now. – Chan Mar 10 '11 at 7:21
You're probably aware of it, but note anyway that this only works because $5$ is prime. – Myself Mar 10 '11 at 7:33

HINT $\rm\ \ x\ p(x)\ =\ 2\ x^4 + 7\ x^2 - 4\ x\ \equiv\ 2\ (x-1)^2\ \ (mod\ 5)\$ for $\rm\ x\not\equiv 0\$ since then $\rm\ x^4\equiv 1\$

-