# Checking a proof of a basic property of prime numbers

1. Dec 3, 2016

### Ghost Repeater

1. The problem statement, all variables and given/known data
Prove: If p is prime and m, n are positive integers such that p divides mn, then either p divides n or p divides m.

Is anyone willing to look through this proof and give me comments on the following: a) my reasoning within the strategy I chose (validity, any constraints or cases I might have missed), b) the strategy I chose (was it a good one, is there a better one, some other angle I might have taken), and c) my presentation (messiness, inelegance)?

2. Relevant equations n/a

3. The attempt at a solution
Here's my proof.

If p divides mn, then there must be some positive integer q such that mn = pq. Then (mn)/q = p is prime. The factors of p are m/q and n. Since p is prime, one of these factors must be equal to 1. Therefore either

a) n = 1

or

b) m/q = 1.

If a) holds, then mn = m = pq and we see that p divides m.

If b) holds, then m = q, and so mn = qn = pq, which means p = n and so p divides n (with quotient of 1).

Therefore, if p divides mn, then either p divides m or p divides n, as desired.

2. Dec 3, 2016

### rcgldr

or p divides both m and n.

3. Dec 3, 2016

### Math_QED

That's not nessecary in the proof. If p divides both m and n, p divides obviously m or n.

4. Dec 3, 2016

### PeroK

You can't conclude that $m/q$ and $n$ are integer factors of $mn/q$.

$q$ might divide neither $m$ nor $n$.

5. Dec 3, 2016

### Ray Vickson

What results do you have available already? What properties are you allowed to use?

6. Dec 3, 2016

### Ghost Repeater

The text I'm using has so far defined the greatest common divisor and gives the theorem (with proof) that two nonzero integers a and b have a unique positive greatest common divisor.

I'll try to use these to make the proof. Thanks!

7. Dec 3, 2016

### Ghost Repeater

I see! Thanks for the heads up!