Proof of Divisibility of k|n Given Relatively Prime k,m

[twoski]

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

Homework Statement

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

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?

 

[tiny-tim]

hi twoski!

… 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.

6 does not divide 9

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

 

[twoski]

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

 

[tiny-tim]

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

your proof doesn't use relative prime-ness

 

[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.

 

[tiny-tim]

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

k does not divide into m. It follows that k|n in order for k|mn to be true.

 

[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?

 

[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

 

[jing2178]

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?

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.

 

[jing2178]

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

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

 

[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