# Simple mod problem, not sure if I'm doing this right, can someone check me please?

• Jan 31st 2010, 09:10 AM
Simple mod problem, not sure if I'm doing this right, can someone check me please?
Determine whether each of these congruences has solutions. If so, find them...

a) x^2 congruent to 1 (mod 3)
b) x^2 congruent to 2 (mod 7)
c) x^2 congruent to 3 (mod 11)

a) I think it is just x=1 (mod 3) or x=2 (mod 3). Since x^2=1 and 1-1=0, which divides 3 and x^2=4 and 4-1=3, which divides 3. Is it that simple or am I doing things wrong?

b) So, this would be, by just checking them all: x=3(mod 7) or x=4 (mod 7)

c) x=2 (mod 11), x=5 (mod 11), x=6 (mod 11) is what I get.

Did I do these right?

Thanks.
• Jan 31st 2010, 09:29 AM
hatsoff
Quote:

Determine whether each of these congruences has solutions. If so, find them...

a) x^2 congruent to 1 (mod 3)
b) x^2 congruent to 2 (mod 7)
c) x^2 congruent to 3 (mod 11)

a) I think it is just x=1 (mod 3) or x=2 (mod 3). Since x^2=1 and 1-1=0, which divides 3 and x^2=4 and 4-1=3, which divides 3. Is it that simple or am I doing things wrong?

b) So, this would be, by just checking them all: x=3(mod 7) or x=4 (mod 7)

c) x=2 (mod 11), x=5 (mod 11), x=6 (mod 11) is what I get.

Did I do these right?

Thanks.

Unfortunately part (c) is not correct.

First, recall the theorem which states that the congruence $f(x)\equiv 0\mod p$, where $f(x)$ is a polynomial of degree $n$ with integral coefficients, has at most $n$ solutions (Niven, An Introduction to the Theory of Numbers, ch. 2, sec. 7). In particular, these quadratic congruences will simply have plus/minus a natural number less than its respective prime.

With that in mind, we needn't perform any detailed calculations. The numbers are small enough that trial-and-error works just fine.

(a) $x\equiv\pm1\mod 3$;

(b) $x\equiv\pm3\mod 7$;

(c) $x\equiv\pm5\mod 11$.

So, in other words, all your answers are correct except that $x\not\equiv 2\mod 11$ in part (c).
• Jan 31st 2010, 09:40 AM
Thanks, but just a little confused. For a), for instance, I just need to write it as either 1 (mod 3), 2 (mod 3) or 1 (mod 3), -1 (mod 3).

I guess since 2(mod 3)=-1(mod 3), but is it usually customary to only write these as positive numbers, or would either be accepted as the answer. Thanks.
• Jan 31st 2010, 09:46 AM
hatsoff
Quote:

Yes, $x\equiv\pm1\mod3$ is logically equivalent to $x\equiv1,2\mod3$, so unless your professor demands you write your congruences a certain way, either one would be acceptable. I happen to prefer the $\pm n$ notation in this context, but if you have the opposite preference, and wish to convert to positive integers, then by all means go nuts!