Ground plan of Forward direction - Let $p$ be an odd prime. Prove $x^{2} \equiv -1 \; (mod \, p)$ has a solution $\iff p\equiv 1 \; (mod 4)$

Prove by contradiction. Thence suppose NOT $p\equiv 1 \; (mod 4)$. Thence 3 possibilities remain: $4|p, 4|(p - 2), 4|(p - 3)$. But $p > 2$ is prime, thence $4 \not | p$.

(1) How can you preconceive to prove by contradiction? Other direction is direct proof.

(2) How can you intuit $4 \not | p - 2$? I can only prove by contradiction. Suppose $4 | p - 2$ for a contradiction. Then there exists a natural number k for which $4k = p -2 \iff 4k + 2 = p$. But $p > 2$ is prime, thence p can't divide an even number. Contradiction.

The only case left is $p\equiv 3 \; (mod 4)$. This means there exists a natural number n such that $4n = p - 3$. Thence $\dfrac{p - 1}{2} = \dfrac{(4n + 3) - 1}{2}$, an even integer.
If $x$ solves $\color{magenta}{x^{2}\equiv -1 \; (mod \, p)}$ , then $x$ is coprime to $p$.

(3). Why write 'If $x$ solves $\color{magenta}{x^{2}\equiv -1 \; (mod \, p)}$ ? This tells nothing? $gcd(\text{ any other integer }, \text{ prime > 2}) = 1$ always?

(4) How to preconceive use of Fermat's Little Theorem?

(5) How can you preconceive the trick to precipitate the second congruence underneath - writing $x^{p-1}$ as $\color{magenta}{(x^{2}})^{ \frac{p - 1}{2} }$?

So use Fermat's Little Theorem \begin{align} 1 & \equiv x^{p-1}\; (mod \, p) \\ & \equiv(\color{magenta}{x^{2}})^{ \frac{p - 1}{2} } \\ & \equiv(\color{magenta}{-1})^{ \frac{p - 1}{2} } \\ & \equiv -1 \; (mod \, p) \quad \text{ because\frac{p - 1}{2}is odd } \end{align}

Since $p$ is odd, thence $p \not | 2$ and the last congruence is a contradiction. Thence no solution.

• For (3) look at the following example: $\gcd(10,5)$. Certainly $5>2$! May 9 '14 at 15:13
• Your first part look sutterly complicated. Primes $\ne 2$ are odd, and odd numbers are either $\equiv 1\pmod 4$ or $\equiv 3\pmod 4$. May 9 '14 at 15:16

Like the proof that you quote, the key ideas behind many elementary number theory proofs are better comprehended only after one learns group theory. The idea behind the quoted proof is that if $$\,x^2\equiv -1\,$$ then $$\,x\,$$ has order $$\,\color{#c00}4,\,$$ thus $$\,x^{p-1}\equiv 1\,\Rightarrow\, \color{#c00}4\mid p-1.\,$$ Said group-theoreoretically, the subgroup $$\,\langle x\rangle\,$$ generated by $$\,x\,$$ must have order being a divisor of the order of the multiplicative group of nonzero elements of $$\,\Bbb F_p,\,$$ by Lagrange's Theorem.