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!