# question on distinct solutions to congruences

• Aug 17th 2008, 12:43 PM
Proggy
question on distinct solutions to congruences
I had 5 problems to find all distinct solutions or show there are none. I did all 5 using a table of x values and just testing each, basically brute forcing them. I seem to be all over the place trying to figure them out in a more efficient manner. Any suggestions on how to do these with a good method would be greatly appreciated:

1.
x^2 + x + 3 = 0(mod 5)

2.
x^2 + 2x + 3 = 0(mod 5)

3.
x^2 = 4(mod 15)

4.
x^2 + x + 4 = 0(mod 8)

5.
x^3 + 2x^2 + 5x + 6 = 0(mod 11)

As I said, I already know the answers from brute forcing and checking the back of the book, but I can not seem to find a consistent, better method, especially for number 5, and this is something I really want to understand how to do.
• Aug 17th 2008, 04:02 PM
Soroban
Hello, Proggy!

I'll help with a few of these.
I'm still working on the others . . .

Quote:

$\displaystyle 1)\;\;x^2 + x + 3 \:\equiv \:0 \pmod{5}$
Note that: .$\displaystyle 1 \equiv -4 \pmod{5}$

So we have: .$\displaystyle x^2 - 4x + 3 \:\equiv\:0 \pmod{5}$

Factor: .$\displaystyle (x - 1)(x - 3)\:\equiv\:0 \pmod{5}$

Therefore: .$\displaystyle \begin{array}{ccccccc}x-1\:\equiv 0\pmod{5} & \Rightarrow & \boxed{x \:\equiv 1\pmod{5}} \\ x -3\:\equiv\:0 \pmod{5}& \Rightarrow & \boxed{x \:\equiv 3\pmod{5}} \end{array}$

Quote:

$\displaystyle 3)\;\;x^2 \:\equiv\:4 \pmod{15}$
We have: .$\displaystyle x \:\equiv \:\pm2\pmod{15}$

Therefore: .$\displaystyle \boxed{x \:\equiv\:2,\:13}$

Quote:

$\displaystyle 4)\;\;x^2 + x + 4 \:\equiv\: 0 \pmod{8}$

Note that: .$\displaystyle 1 \:\equiv -7\:\text{ and }\: 4 \:\equiv\:12 \pmod{8}$

So we have: .$\displaystyle x^2 - 7x + 12 \:\equiv\:0 \pmod{8}$

Factor: .$\displaystyle (x-3)(x-4) \:\equiv\:0 \pmod{8}$

Therefore: .$\displaystyle \boxed{x \:\equiv\:3,\:4} \pmod{8}$

• Aug 17th 2008, 04:40 PM
Soroban
Hello again, Proggy!

I just saw through the last one . . .

Quote:

$\displaystyle 5)\;\;x^3 + 2x^2 + 5x + 6 \:\equiv\: 0 \pmod{11}$

Note: . $\displaystyle 2\:\equiv\:-9.\;\; 5 \:\equiv\:27,\;\;6 \:\equiv\:-27 \pmod{11}$

So we have: . $\displaystyle x^3 - 9x^2 + 27x - 27 \:\equiv\:0 \pmod{11}$

Factor: . $\displaystyle (x - 3)^3 \:\equiv\:0 \pmod{11}$

Therefore: . $\displaystyle \boxed{x\:\equiv\:3\pmod{11}}$

• Aug 17th 2008, 04:42 PM
Proggy
Hi Soroban and thanks for the help!

For 1, I actually did this similar by changing it to be x^2 + x - 2 to get factors of (x+2)(x-1), resulting in the same answer.

Attempting to use the same method on successive problems is why I discarded it as possibly not the best way. Number 3 is the perfect example. You got the +/-2 part, but there is an additional answer of +/-7 that works as well. I ended up working the problem with mod 3 and mod 5 and brute forcing 3 and 5 values respectively. Then I took the common values mod 15 and tested all of them to see which ones worked. Basically a more efficient brute force technique, but still not very efficient as the mod value increases.

For number 4, do you just have to basically know which numbers to change to make it factor or is there a way to help you choose?
• Aug 17th 2008, 04:47 PM
Proggy
Quote:

Originally Posted by Soroban
Hello again, Proggy!

I just saw through the last one . . .

Note: . $\displaystyle 2\:\equiv\:-9.\;\; 5 \:\equiv\:27,\;\;6 \:\equiv\:-27 \pmod{11}$

So we have: . $\displaystyle x^3 - 9x^2 + 27x - 27 \:\equiv\:0 \pmod{11}$

Factor: . $\displaystyle (x - 3)^3 \:\equiv\:0 \pmod{11}$

Therefore: . $\displaystyle \boxed{x\:\equiv\:3\pmod{11}}$

Okay, so it looks like you just have to play around with it until you recognize a factorable equation? I brute forced all 11 possible incongruent numbers and found that only x congruent 3 (mod 11) worked. Your method is obviously better, but what if I don't immediately recognize the equation that you saw?