# Homework Help: Divisibility Proof

1. Nov 11, 2012

### twoski

I think my answer is correct, i just need some peer review.

1. The problem statement, all variables and given/known data

Let k, m, n ∈ Z+ where k and m are relatively prime. Prove that if k|mn then k|n

3. The attempt at a solution

This question seems trivial.

We know the property that if x|y then x|yz for all integers z.

Therefore, if k and m are relatively prime, it follows that k does not divide into m. It follows that k|n in order for k|mn to be true.

Using the property i mentioned, we conclude that k|n.

Is this a proper proof?

2. Nov 11, 2012

### tiny-tim

hi twoski!
6 does not divide 9

for 6 to divide 9*2, does it follow that 6 divides 2 ?

3. Nov 11, 2012

### twoski

But, 6 and 9 are not relatively prime, so we can't use those numbers to test my proof can we?

4. Nov 11, 2012

### tiny-tim

your proof doesn't use relative prime-ness

5. Nov 11, 2012

### twoski

Maybe i'm not being as verbose as i should be, apologies.

Let k, m, n ∈ Z+ where k and m are relatively prime.

We know the property that if x|y then x|yz for all integers x,y,z.

Therefore, if k and m are relatively prime, it follows that k does not divide into m. It follows that k|n in order for k|mn to be true.

Using the property i mentioned, we conclude that if k|mn is true if and only if k|n is true.

6. Nov 11, 2012

### tiny-tim

this part of your proof is not true (and does not mention relative prime-ness) …

7. Nov 11, 2012

### twoski

If k and m are relatively prime, then it follows that their gcd is 1 and therefore k does not divide into m, right? Or did i miss something.... Is k allowed to be 1?

8. Nov 12, 2012

### Bonaparte

I think a easier way, or more formal, to show that k|mn, is to factor it into k| m*n, k does not divide into m (as they are relatively prime), however k|n, so we can "cancel out" to get m*x, where x*k=n. It follows than that for k|mn, k|n must be true.

Bonaparte

Last edited: Nov 12, 2012
9. Nov 12, 2012

### jing2178

What you are missing is some logical steps.

You use relative-primeness to show that k does not divide m which is true. However you then forget about relative primeness and imply that k not dividing into m is sufficient to show tha k|n however as Tiny-Tim pointed out this is not sufficient. You need to use that k and m are relatively prime beyond the fact that this implies k does not divide m.

Think about the prime factors of k and m.

Last edited: Nov 12, 2012
10. Nov 12, 2012

### jing2178

You state however k\n .... it follows....k|n

Again you only use k relative prime to m only to state that k does not divide m this is not sufficient

11. Nov 12, 2012

### Bonaparte

Let me rephrase then, not only that k|m is false, but also they have no common factors other then 1, that is the fraction is at its simplest form, therefore if for some n k|mn, n must by x*k,so that all the factors of k are included in n, note that it doesn't mean they are equal, just that k factors are a subset of n's factors, and when factors of a number are a subset of the factors of another number, the first divides the second, and in the case they have the same factors, the second also divides the first, it then follows that k|n.

How is that?

Bonaparte