# find solution set for this linear congruence

• Nov 2nd 2009, 05:39 PM
jmedsy
find solution set for this linear congruence
$x^2-2$ is congruent to $0(mod7)$
• Nov 2nd 2009, 08:20 PM
alexmahone
Quote:

Originally Posted by jmedsy
$x^2-2$ is congruent to $0(mod7)$

Note that $3^2-2=7=0 (mod\ 7)$ and $4^2-2=14=0 (mod\ 7)$.
So $x=3 (mod\ 7)$ or $x=4 (mod\ 7)$.
• Nov 2nd 2009, 08:41 PM
jmedsy
thanks
• Nov 2nd 2009, 08:43 PM
alexmahone
Quote:

Originally Posted by jmedsy
That's true, but its also true for x = 10. How can I solve for all possible x?

10 falls into the solution set $x=3 (mod\ 7)$.
• Nov 2nd 2009, 08:52 PM
jmedsy
Quote:

Originally Posted by alexmahone
10 falls into the solution set $x=3 (mod\ 7)$.

Once you had determined that x=3 or x=4 satisfied the congruency, did you continue to check congruency for greater x? How did you know when to stop?
• Nov 2nd 2009, 09:01 PM
alexmahone
Quote:

Originally Posted by jmedsy
Once you had determined that x=3 or x=4 satisfied the congruency, did you continue to check congruency for greater x? How did you know when to stop?

You need to check congruency only for x ranging from 0 to 6. (If the modulus was n, you should have checked for x ranging from 0 to n-1.)
• Nov 2nd 2009, 09:03 PM
jmedsy
right, that makes sense. Is there any correlation between the degree of that polynomial and the number of different modular congruences between 0 and 6?