# Number Theory: Divisibility Proof

## Homework Statement

Show that if $p$ is an odd prime of the form $4k + 3$ and $a$ is a positive integer such that $1 < a < p - 1$, then $p$ does not divide $a^2 + 1$

## Homework Equations

If $a$ divides $b$, then there exists an integer $c$ such that $ac = b$.

## The Attempt at a Solution

We have to do this proof by contradiction, so suppose $p$ divides $a^2 + 1$. Then there exists an integer $c$ such that $pc = a^2 + 1$. At this point I am stuck. I can't factor anything, and I don't see any other algebraic manipulations that will help. Any ideas?