1. ## proof

Let m, n and p be integers, with p prime. Prove that if p divides mn then p divides m or p divides n.

Let m, n and p be integers, with p prime. Prove that if p divides mn then p divides m or p divides n.

In many cases this is jsut the definition of prime number, so: what's the definition you're using?

Tonio

3. Originally Posted by tonio
In many cases this is jsut the definition of prime number, so: what's the definition you're using?

Tonio
Perhaps this is one of the first corollaries of the definition of a prime number, but I haven't seen a prime number defined this way. This problem is called Euclid's Lemma I believe.

4. the definition of prime number i am using is that is a number whose only divisors are 1 and itself

how can I prove this without using Bezout's Identy about relative primes.

the definition of prime number i am using is that is a number whose only divisors are 1 and itself
tonio appears to be busy, so I'll give you a link to look at. This is a standard proof of this problem, but uses another lemma which you may not have covered and be allowed to use.

Euclid's lemma - Wikipedia, the free encyclopedia

6. Originally Posted by tonio
In many cases this is jsut the definition of prime number, so: what's the definition you're using?

Tonio
I was mistaken, my apologies. I have found multiple sources defining prime numbers this way.

Assume p|mn, thus for some integer q, pq=mn. By definition of prime, the gcd(m,p)=1 or gcd(m,p)=p. If gcd(m,p)=p, then p|m and the desired result is shown. If gcd(m,p)=1, then p|gcd(m,p)n. See here for a proof.

Here is the whole proof I outlined above. I'm sorry to link so much but I don't really know what you can use or not so I don't want to type out a bunch of stuff for nothing. Does the above info help?

the definition of prime number i am using is that is a number whose only divisors are 1 and itself.
Originally Posted by Jameson
I was mistaken, my apologies. I have found multiple sources defining prime numbers this way.
There are multiple sources that use that definition. I even hear Keith Devlin use it.
But nonetheless, strictly speaking it is incorrect.
That definition makes 1 a prime number.
The number 1 has only 1 and itself as divisors.

So I think that the correct wording is: A positive integer is prime if and only if it has exactly two divisors.
You understand that 1 has only one divisor: itself.

8. Ok, ok, I get what you mean. All that is needed is to add "distinct" to that definition to make it such that 1 isn't prime.

9. Originally Posted by Jameson
Ok, ok, I get what you mean. All that is needed is to add "distinct" to that definition to make it such that 1 isn't prime.
Well 16 has two distinct divisors: {1,16}, or {2,8} or {4,16}.
So we need the word exactly.

10. p|gcd(m,p)n.

how do you prove this step in your proof jameson