# Thread: question on distinct solutions to congruences

1. ## 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.

2. Hello, Proggy!

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

$\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}$

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

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

$\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}$

3. Hello again, Proggy!

I just saw through the last one . . .

$\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}}$

4. 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?

5. 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?