Use Proposition 30 in book VII of Euclids Elements to prove

Use Proposition 30 in book VII of Euclid\'s Elements to prove the following: Let m,n,k be natural numbers and let p be a prime; if p divides mnk, then p must divide at least one of m,n, or k. First use prop 20, Book VII of Euclid\'s Elements to show that if p is a prime that divides (mn)k, then p divides mn or p divides k.

If someone could do this for me with work I would really appreciate it. I want to see the correct process to help me with my other problems. Thanks.

Solution

Given that p divides mnk

we can also write that as p|mnk

since multiplication of natural numbes is associative then

p|(mn)k

then by proposition 30 we get p|mn or p|k.

if p|k is true then we have proved that \"if p divides mnk, then p must divide at least one of m,n, or k\"

say p|k is false then p|mn is true

again apply proposition 30 on p|mn we get p|m or p|n

if p|m is false then p|n must be true.

if p|n is false then p|m must be true.

So in any case we are getting one of them true.

Hece it is proved that \"if p divides mnk, then p must divide at least one of m,n, or k\"