# Congruence equation

Printable View

• Oct 17th 2010, 08:12 PM
I-Think
Congruence equation
Good day to the MHF. Here's my problem
Find all integer solutions to $x^{19}+3x^2\equiv10$ $(mod$ $21)$

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

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

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

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

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

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

And a solution to our original equation is $x\equiv67$ $(mod$ $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.
• Oct 18th 2010, 07:26 AM
Soroban
Hello, I-Think!

You're off to a good start . . .

Quote:

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

Just making sure my solution is complete

Solution

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

By CRT, we can break this up to: . $\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 $x^{19}+3x^2 \:\equiv\:10 \text{ (mod 3)}$
we use FLT to simplify: . $x^2\:\equiv\: 1 \text{ (mod 3)}$

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

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

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

Quote:

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

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

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

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

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

. . $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)}}$

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

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