1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    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!

Homework Help: Proof about primes and gcd

  1. Jul 17, 2011 #1
    1. The problem statement, all variables and given/known data

    prove that p is prime iff for any integer "a" either (a,p)=1 or p divides a

    (where (a,p) denotes the gcd of a and p)

    2. Relevant equations

    (a,b)= the greatest common factor of a and b

    3. The attempt at a solution

    I had no trouble with proving the forward direction of the statement. But for the backward direction, here is what I have:

    for any integer "a", let either (a,p)=1 or p divide a
    Now assume that p is not prime.
    The following must hold true:
    either (6,4)=1 or 4 divides 6
    Since both of these statements are false, this is a contradiction.
    Therefore p must be prime.

    It seems okay to me to use an example at this point to arrive at the contradiction. Is this a legitimate way to prove the theorem?
  2. jcsd
  3. Jul 17, 2011 #2


    User Avatar
    Homework Helper

    No. You want to show this works for all (a,p). You're on the right track wanting to show by contradiction, but try this instead:

    Case 1: Let (a,p) = 1, p does not divide a and assume to contrary that p is not prime. So p = xy, x,y > 1. How can we get a contradiction?

    Case 2: Let (a,p) != 1, p divide a and assume to contrary that p is not prime. So p = xy, x,y > 1. How can we get a contradiction?
  4. Jul 17, 2011 #3
    Ok thank you. That seems a much better way to prove this. However, I am still not seeing the logical flaw in the argument I used. If you let "(a,p)=1 or p divide a", and assume that p is not prime, isn't an example of a contradiction enough to conclude that the assumption was false?
  5. Jul 17, 2011 #4


    User Avatar
    Homework Helper

    I see what you're talking about now.

    This unfortunately won't work. You've shown that you obtain a contradiction only for that example (which is good). However, assuming that we did it your way, how do we know that there don't exist examples where there's not a contradiction and the example satisfies all three statements?

    By keeping things general, you'll be able to show that you'll obtain a contradiction for every time you choose p to not be prime.
  6. Jul 17, 2011 #5
    I think this only works when you're making a statement about all non-primes having those properties. That is, your counterexample must be against a statement that says "for all non-prime p, (a,p)=1 or p divides a". However, in your statement, you're only assuming that there might exist one such p that isn't prime with those properties, and so a counter example would not show that the statement is wrong (just that the p you chose doesn't fit the description; there are still infinitely many p to choose from that aren't prime that might fit your requirements).

    Against a "for all" statement, such as for all [itex]f[/itex] that are continuous at any number of points, [itex]f[/itex] is differentiable at those points, you can provide a counter example ([itex]f(x) = |x|[/itex] works here) and that takes care of the problem.
    However, for a "there exists" statement, such as "[itex]\exists \delta \; s.t.\; \forall \varepsilon > 0, |x-x_0| < \delta \implies |f(x)-L|<\varepsilon[/itex]
    If you just pick [itex]\delta = 100[/itex], it probably wouldn't work for the implication, but would that disprove that limit, or would there still be a possibility that [itex]\delta = 99[/itex] would work? If not, would 98? 97? etc
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook