Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook