Thread: 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.

Originally Posted by twittytwitter

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 , where is a polynomial of degree with integral coefficients, has at most 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) ;

(b) ;

(c) .

So, in other words, all your answers are correct except that in part (c).

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.

Originally Posted by twittytwitter

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.

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

Gotcha, thanks. Yeah, my professor writes the positives only when in class, which is why I wasn't sure.