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

1. ## 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.

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 $\displaystyle f(x)\equiv 0\mod p$, where $\displaystyle f(x)$ is a polynomial of degree $\displaystyle n$ with integral coefficients, has at most $\displaystyle 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) $\displaystyle x\equiv\pm1\mod 3$;

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

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

So, in other words, all your answers are correct except that $\displaystyle x\not\equiv 2\mod 11$ in part (c).

3. 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, $\displaystyle x\equiv\pm1\mod3$ is logically equivalent to $\displaystyle 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 $\displaystyle \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!