How to solve a congruence of a polynomial $x^3+2x^2+x+2\equiv 0 \mod 45$?

1.2k Views Asked by At

$x^3+2x^2+x+2\equiv 0 \mod 45$

$f(x)=(x^2+1)(x+2)$

by inspection

$\fbox{1}$$x=7$ is a possible solution $\mod 9$ ,since $45=5\times 3^2$

$\fbox{2} $ $x= 2 $ is a solution $\mod 5$ but i want to get general work on how to find other solutions...from here >>>

2

There are 2 best solutions below

0
On

If you want to solve it without explicitly stating the Chinese Remainder Theorem.

Hint :$ x \equiv 7 \pmod 9$ so $ x = 9k+ 7 $ for some $k$.

Now, $ 9k + 7 \equiv ? \pmod 5$.

Solve for $k$.

0
On

First work with modulo 9:

$$f(x) = (x^2 + 1)(x + 2) \equiv 0 \pmod 9$$

Now we have three distinct cases, because 9 is square of 3:

Case 1: $9\mid (x^2 + 1)$

This case is impossible, because $-1$ isn't quadratic residue modulo $9$.

Case 2: $3\mid (x^2 + 1)$ and $3\mid (x+2)$

The first relation is impossible, because $-1$ isn't quadratic residue modulo $3$.

Case 3: $9\mid (x+2)$

This is the only case possible and is satisfied when $x \equiv 7 \pmod 9$

So this implies that $f(x) \equiv 0 \pmod 9$ if and if $x \equiv 7 \pmod 9$

Now work modulo 5:

$$f(x) = (x^2 + 1)(x + 2) \equiv 0 \pmod 5$$

Because $5$ is prime number we have only two cases:

Case 1: $5\mid (x^2+1)$

We know that $-1$ is quadratic residue modulo $5$ and it implies that $x \equiv \pm 2 \pmod 5$

Case 1: $5\mid (x+2)$

This one implies that $x \equiv -2 \pmod 5$

So from this we obtain that $f(x) \equiv 0 \pmod 5$ if and only if $x \equiv \pm 2 \pmod 5$

Now apply Chinese Remainder Theorem for two cases:

Case 1: $x \equiv 2 \pmod 5$ and $x \equiv 7 \pmod 9$

The first conguence relation is equivalent to $x \equiv 7 \pmod 5$, so using this and the second congruence relation $x \equiv 7 \pmod {45}$

Case 2: $x \equiv -2 \pmod 5$ and $x \equiv 7 \pmod 9$

Applying CRT we get that $x \equiv -2 \equiv 43 \pmod {45}$

So we have two solutions:

$$x \equiv 7,43 \pmod {45}$$