1. PF Contest - Win "Conquering the Physics GRE" book! Click Here to Enter
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Number Theory: Divisibility Proof

  1. Mar 15, 2012 #1
    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?
  2. jcsd
  3. Mar 15, 2012 #2
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook