(adsbygoogle = window.adsbygoogle || []).push({}); 1. The problem statement, all variables and given/known data

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

2. Relevant equations

If [itex]a[/itex] divides [itex]b[/itex], then there exists an integer [itex]c[/itex] such that [itex]ac = b[/itex].

3. The attempt at a solution

We have to do this proof by contradiction, so suppose [itex]p[/itex] divides [itex]a^2 + 1[/itex]. Then there exists an integer [itex]c[/itex] such that [itex]pc = a^2 + 1[/itex]. 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?

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Number Theory: Divisibility Proof

**Physics Forums | Science Articles, Homework Help, Discussion**