# Number Theory: Divisibility Proof

1. Mar 15, 2012

### tylerc1991

1. The problem statement, all variables and given/known data

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$

2. Relevant equations

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

3. 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?

2. Mar 15, 2012