Number theory lemma - $x^2 \equiv 1 \pmod p$ implies $x\equiv\pm 1\pmod p$ The proof is a follows:
Let $p$ be a prime number and $x$ in Z. If $x^2\equiv1\pmod p$ then $x\equiv\pm1\pmod p$.
Proof: By assumption, $p | x^2 - 1 = (x + 1)(x - 1)$. Thus $p | x + 1$ or $p | x - 1$. This completes the proof.

However if $p | x + 1$ then $x$ is congruent to $-1 \mod p$. However why is $p$ congruent to $1 \mod p$ ?? 
I'm struggling seeing this, and been sitting for some hours now trying to figure it out - please help.
 A: Perhaps it is easier to view this as euqation $x^2-1=0$ over the finite field $\mathbb{F}_p$.
Since $0=x^2-1=(x+1)(x-1)$, and the field has no zero divisors, we must have either $x=1$ or $x=-1$ in $\mathbb{F}_p$. This means $x\equiv 1(p)$ or $x\equiv -1(p)$.
A: To show that the solutions of $x^2\equiv 1\pmod{p}$ are $x\equiv \pm 1$ actually requires that we prove two things. 
We must show that (i) $x\equiv 1\pmod{p}$ is a solution, and $x\equiv -1\pmod{p}$ is a solution.
We must also show that (ii) there are no other solutions modulo $p$.
Proving (i) is easy. All we need to do is to verify that $(1)^2\equiv 1\pmod{p}$ and $(-1)^2\equiv 1 \pmod{p}$. 
Note that if $p=2$ the two solutions are the same. For $1\equiv -1\pmod{2}$.
We now turn to the proof of (ii). We know that if  $x^2\equiv 1\pmod{p}$, then  $p$ divides $x^2-1$, and therefore $p$ divides $(x-1)(x+1)$.
Since $p$ is prime, and divides $(x-1)(x+1)$, we must have (a) $p$ divides $x-1$ or (b) $p$ divides $x+1$.
In Cae (a), we have $x\equiv 1\pmod{p}$. In Case (b), we have $x\equiv -1\pmod{p}$. There are no other possibilities.
Remark: Note that if $p$ is composite, then the result can fail. For example, the congruence $x^2\equiv 1\pmod{8}$ has four solutions modulo $8$, namely $x\equiv \pm 1\pmod{8}$, and $x\equiv \pm 3\pmod{8}$. 
