Proving an integer is prime


by Cableguy008
Tags: integer, prime, proving
Cableguy008
Cableguy008 is offline
#1
Sep12-05, 05:59 AM
P: 3
Hey there, I've been having some problems trying to prove this:

"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.]"

Proving p *can* be prime isn't too difficult, but proving p *must* be prime has really confused me.

I've tried going down the path, gcd(p,b) = p if p | b. Which means p = pn + bm, but since b = px, p = pn + pxm = p(n + mx) => n + mx = 1. This doesn't seem to get me anywhere though.

Then I've tried using b = pn, c = pm and tried various manipulations such as b / n = c / m => bm = cn = pmn but I just don't see how I can get it in the form p = dt.

Now, if I got it to the form p = dt, I'm not sure how I could prove p must be prime. Who's to say its not prime? I don't know it seems like I'm thinking in circles here. (Sorry for not properly defining n,m and x I just assumed they were integers to save time). Any help would be greatly appreciated. Unfortunately my professor has been out of town for the entire week so I've been unable to seek help from him (its still due though of course :P).
Phys.Org News Partner Science news on Phys.org
SensaBubble: It's a bubble, but not as we know it (w/ video)
The hemihelix: Scientists discover a new shape using rubber bands (w/ video)
Microbes provide insights into evolution of human language
HallsofIvy
HallsofIvy is offline
#2
Sep12-05, 06:30 AM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 38,900
Suppose p is NOT a prime. Then p= mn for some integers m and n. Let b= m, c= n.

bc= mn is divisible by p but neither b nor c are.
shmoe
shmoe is offline
#3
Sep12-05, 08:58 AM
Sci Advisor
HW Helper
P: 1,996
Use their hint. If p=dt then you know p|d or p|t, assume it's the former. So p|d and d|p, which is larger in absolute value, d or p?

Cableguy008
Cableguy008 is offline
#4
Sep12-05, 02:49 PM
P: 3

Proving an integer is prime


"Use their hint. If p=dt then you know p|d or p|t, assume it's the former. So p|d and d|p, which is larger in absolute value, d or p?"

Ok so since p = dt (or nm) p / d = t, since t is an int d | p. If p | d, d / p = 1 / t, so t = +/- 1 and thus d = +/- p. Conversely if p | t, WLOG t = +/- p, d = +/- 1. So d = +/- p or +/- 1 and p is prime. Is this correct?
shmoe
shmoe is offline
#5
Sep12-05, 03:15 PM
Sci Advisor
HW Helper
P: 1,996
Quote Quote by Cableguy008
"Use their hint. If p=dt then you know p|d or p|t, assume it's the former. So p|d and d|p, which is larger in absolute value, d or p?"

Ok so since p = dt (or nm) p / d = t, since t is an int d | p. If p | d, d / p = 1 / t, so t = +/- 1 and thus d = +/- p. Conversely if p | t, WLOG t = +/- p, d = +/- 1. So d = +/- p or +/- 1 and p is prime. Is this correct?
Looks good, though not exactly what I had in mind. If a|b then a<=b, etc (assuming a, b positive-it's such a pain to work with the integers instead of the naturals here, note there should also be a requirement that p is positive if you mean it to be a prime in the usual sense).
Cableguy008
Cableguy008 is offline
#6
Sep12-05, 06:27 PM
P: 3
Thanks for the input you two, you've truly helped out.


Register to reply

Related Discussions
Proof Question: Prove integer + 1/2 is not an integer Calculus & Beyond Homework 4
proving/disproving n^2-n+11 is prime, i think i got it Calculus & Beyond Homework 4
proving statements, having issues finding distinct integers and also prime question Calculus & Beyond Homework 3
A formula of prime numbers for interval (q; (q+1)^2), where q is prime number. Linear & Abstract Algebra 0
Efficiency: prime test vs prime generator Linear & Abstract Algebra 14