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 $\displaystyle \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 $\displaystyle n=$ of the polynomial different roots, so $\displaystyle 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 $\displaystyle \mathbb{Z}\slash 8\mathbb{Z}$ which fulfill $\displaystyle x^2=1\!\!\!\pmod 8$

Tonio