# Proving an integer is prime

• Sep 12th 2005, 03:39 AM
Cableguy
Proving an integer is prime
I'm having some trouble with this proof problem. Anyone have any ideas?

"Let p be an integer other than 0, +/- 1 with this property: Whenever b and c are integers such that p | bc, then p | b or p | c. Prove p is prime. [Hint: If d is a divisor of p, say p = dt, then p | d or p | t. Show that this implies d = +/- p or d = +/- 1.]

I know how to prove p *can be* a prime, however I've been unable to prove p *must* be a prime. I was thinking of using gcd(p, b) = p if p | b (and vice versa). Then p = pn + bm. But I'm unable to come up with anything. In the hint it claims to show this is true if d is a divisor of p, but I'm not sure how to even get there. Any help would be appreciated!
• Sep 12th 2005, 02:38 PM
rgep
Suppose that p has the property p | ab implies p | a or p | b (or both). Now let d be a divisor of p. Then p = de for some e: note that e is also a divisor of p. So in particular p | de and so p | d or p | e. We are in the situation where f | p and p | f, where f is either d or e. But if p = fu and f = pv then p = puv. So uv=1 and u,v are integers, so u,v = +- 1. So if d | p then either d = +-1 or d = +- p. But this means that p is prime, that is, has no non-trivial divisors.
• Sep 12th 2005, 04:25 PM
Cableguy
Much appreciated, in my other thread (http://www.physicsforums.com/showthread.php?t=88585) I came up with a similiar solution. I think yours is probably better hehe.

Thanks again.