Thread: Quadratic Equations in mod 13

I would like some help with this question:

Q: x^2+x+1=0 (mod 13)

I can't factorise the LHS as it stands, so I changed the 0 to 13, rearrange to give:

x^2+x-12=0 (mod 13)

(x+4)(x-3)=0 (mod 13)

so:
x=-4 or 3 (mod 13)

Does my method work or have I gone wrong somewhere? Pointers would be greatly appreciated.

Looks good. My only comment is that if you're using mod 13, you should change the -4 to a 9.

Thanks.

Just wondering, this question only worked because I could factorise the LHS after changing 0 on the RHS to 13, what would happen if the LHS couldn't be factorised? Is there anyway I'd be able to solve for x?

Sort of.

You can always manipulate your constant term to a place where there are solutions within the range, like you did. It's a matter of making your determinant, , nonnegative.

However, it is possible that you will end up with non-whole number solutions, which may or may not be okay, depending on how strict you are with your modular definitions.

Originally Posted by free_to_fly

I would like some help with this question:

Q: x^2+x+1=0 (mod 13)

I can't factorise the LHS as it stands, so I changed the 0 to 13, rearrange to give:

x^2+x-12=0 (mod 13)

(x+4)(x-3)=0 (mod 13)

so:
x=-4 or 3 (mod 13)

Does my method work or have I gone wrong somewhere? Pointers would be greatly appreciated.

Your method is fine. You can plug your answers back into the original equation and see that they check. The quadratic formula works fine too, providing b^2 - 4ac has a square root in the field, and not everything does.

Completing the square works fine too, but not everything has a square root.

For example, consider x^2 + 4x + 6 = 0. If we try to complete the square we get first x^2 + 4x = -6 or x^2 + 4x + 4 = -6 +4 or (x+2)^2 = -2, or equivalently (x+2)^2 = 11. But there no integer whose square is 11 mod 13, so this equation has no solution.