# Thread: Congruence equation

1. ## Congruence equation

Good day to the MHF. Here's my problem
Find all integer solutions to $\displaystyle x^{19}+3x^2\equiv10$ $\displaystyle (mod$ $\displaystyle 21)$

Just making sure my solution is complete
Solution
$\displaystyle x^{19}+3x^2\equiv10$ $\displaystyle (mod$ $\displaystyle 21)$
By CRT, we can break this up to
$\displaystyle x^{19}+3x^2\equiv10$ $\displaystyle (mod$ $\displaystyle 3)$
$\displaystyle x^{19}+3x^2\equiv10$ $\displaystyle (mod$ $\displaystyle 7)$

And now we deal with each separately
For $\displaystyle x^{19}+3x^2\equiv10$ $\displaystyle (mod$ $\displaystyle 3)$
we use FLT to simplify: $\displaystyle x^2\equiv 1$ $\displaystyle (mod$ $\displaystyle 3)$
Simplifying
$\displaystyle x+3\equiv10$ $\displaystyle (mod$ $\displaystyle 3)$. Solves to give $\displaystyle x\equiv7$ $\displaystyle (mod$ $\displaystyle 3)$

Now dealing with
$\displaystyle x^{19}+3x^2\equiv10$ $\displaystyle (mod$ $\displaystyle 7)$
FLT: $\displaystyle x^6\equiv1$ $\displaystyle (mod$ $\displaystyle 7)$
Simplifying
$\displaystyle 3x^2+x\equiv10$ $\displaystyle (mod$ $\displaystyle 7) \rightarrow$, we solve this via guesswork

Let $\displaystyle 3x^2+x-10=14\rightarrow3x^2+x-24=0$
$\displaystyle (3x-8)(x+3)=0$Solution: $\displaystyle x\equiv-3$ $\displaystyle (mod$ $\displaystyle 7)$

So now we use CRT to solve
$\displaystyle x\equiv7$ $\displaystyle (mod$ $\displaystyle 3)$
$\displaystyle x\equiv-3$ $\displaystyle (mod$ $\displaystyle 7)$
$\displaystyle x-7=3m$$\displaystyle x+3=7n$

$\displaystyle 7n-3m=10$ Solve to get $\displaystyle m=20, n=10$
So $\displaystyle x=67$

And a solution to our original equation is $\displaystyle x\equiv67$ $\displaystyle (mod$ $\displaystyle 21)$

Is this all the solutions or am I missing some? If so, where is te error in my method preventing me from obtaining the others?
Thanks in advance for the help.

2. Hello, I-Think!

You're off to a good start . . .

Find all integer solutions to: .$\displaystyle x^{19}+3x^2\:\equiv\:10\text{ (mod 21)}$

Just making sure my solution is complete

Solution

$\displaystyle x^{19}+3x^2\equiv10$ $\displaystyle (mod$ $\displaystyle 21)$

By CRT, we can break this up to: .$\displaystyle \begin{Bmatrix}x^{19}+3x^2\:\equiv\:10 \text{ (mod 3)} \\ x^{19}+3x^2\:\equiv\:10 \text{ (mod 7)} \end{Bmatrix}$

And now we deal with each separately

For $\displaystyle x^{19}+3x^2 \:\equiv\:10 \text{ (mod 3)}$
we use FLT to simplify: .$\displaystyle x^2\:\equiv\: 1 \text{ (mod 3)}$

Simplifying: .$\displaystyle x+3 \:\equiv\:10 \text{ (mod 3)}$.

Solve to give: .$\displaystyle x\:\equiv\:7 \text{ (mod 3)}$

Hence, we have: .$\displaystyle \boxed{x \:\equiv\:1\text{ (mod 3)}}$

Now dealing with: .$\displaystyle x^{19}+3x^2\:\equiv\:10 \text{ (mod 7)}$

FLT: .$\displaystyle x^6\:\equiv\:1 \text{ (mod 7)}$

Simplifying: .$\displaystyle 3x^2+x \:\equiv\:10 \text{ (mod 7)}$

We have: .$\displaystyle 3x^2 + x - 10 \:\equiv\:0\text{ (mod 7)}$

Factor: .$\displaystyle (x+2)(3x-5) \:\equiv\:0\text{ (mod 7)}$

. . $\displaystyle x+2\:\equiv\:0\text{ (mod 7)} \quad\Rightarrow\quad x \:\equiv\:-2\text{ (mod 7)} \quad\Rightarrow\quad \boxed{x \:\equiv\:5\text{ (mod 7)}}$

. . $\displaystyle 3x-5\:\equiv\:0\text{ (mod 7)} \quad\Rightarrow\quad 3x \:\equiv\:5\text{ (mod 7)}$

. . Multiply by 5: .$\displaystyle 15x\:\equiv\:25\text{ (mod 7)} \quad\Rightarrow\quad \boxed{x \:\equiv\:4\text{ (mod 7)}}$