find solution set for this linear congruence

Printable View

November 2nd 2009, 05:39 PM
jmedsy

find solution set for this linear congruence

$x^2-2$ is congruent to $0(mod7)$
November 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)$ .
November 2nd 2009, 08:41 PM
jmedsy

thanks
November 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)$ .
November 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?
November 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.)
November 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?

All times are GMT -8. The time now is 06:02 AM.