# find solution set for this linear congruence

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

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

Note that \$\displaystyle 3^2-2=7=0 (mod\ 7)\$ and \$\displaystyle 4^2-2=14=0 (mod\ 7)\$.
So \$\displaystyle x=3 (mod\ 7)\$ or \$\displaystyle 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 \$\displaystyle x=3 (mod\ 7)\$.
• Nov 2nd 2009, 08:52 PM
jmedsy
Quote:

Originally Posted by alexmahone
10 falls into the solution set \$\displaystyle 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?