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