# Thread: Congruence problems

1. ## Congruence problems

hi everyone

anyone up for taking a look at these congruence proofs? ;3

5. (a) Prove that if p is a prime, then the only solutions of x^2 congruent to 1 (mod p) are integers x such that x congruent to 1 (mod p) or x congruent to −1 (mod p).

(b) Suppose that p is not a prime. Then does the statement stay valid, i.e., the only solutions of x^2 congruent to 1 (mod p) are integers x such that x congruent to 1 (mod p) or x congruent to −1 (mod p). Give a
proof or a counterexample.

2. Originally Posted by jessicafreeman
hi everyone

anyone up for taking a look at these congruence proofs? ;3

5. (a) Prove that if p is a prime, then the only solutions of x^2 congruent to 1 (mod p) are integers x such that x congruent to 1 (mod p) or x congruent to −1 (mod p).

The quotient ring $\mathbb{F}_p:=\mathbb{Z}\slash p\mathbb{Z}\,,\,\,p$ a prime, is in fact a field, and thus any polynomial with coefficients in it has at most $n=$ of the polynomial different roots, so $x^2=1\!\!\!\pmod p\Longleftrightarrow (x-1)(x+1)=0\!\!\!\pmod p \Longleftrightarrow x=\pm 1 \!\!\!\pmod p$

(b) Suppose that p is not a prime. Then does the statement stay valid, i.e., the only solutions of x^2 congruent to 1 (mod p) are integers x such that x congruent to 1 (mod p) or x congruent to −1 (mod p). Give a
proof or a counterexample.

Count how many elements are there in $\mathbb{Z}\slash 8\mathbb{Z}$ which fulfill $x^2=1\!\!\!\pmod 8$

Tonio

.

3. Originally Posted by tonio
.
I am having trouble understanding your solution to (a), possibly because i am dumb. Can you please explain it in a different fashion.

4. Originally Posted by DKman
I am having trouble understanding your solution to (a), possibly because i am dumb. Can you please explain it in a different fashion.

Let's try this as follows, which is basically the same way but with more detail, doing operations modulo p all the way long:

$x^2=1\Longleftrightarrow x^2-1=0\Longleftrightarrow (x-1)(x+1)=0$ .

Since $\mathbb{F}_p:=\mathbb{Z}\slash p\mathbb{Z}$ is a field (in fact it is enough that it is an integral domain), the last equality above is possible iff $x=1\,\,\,or\,\,\,x=-1$ , otherwise we'd have non-trivial divisors of zero.

Tonio