1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Divisibility Proof

  1. Nov 11, 2012 #1
    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. jcsd
  3. Nov 11, 2012 #2

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    hi twoski! :smile:
    6 does not divide 9

    for 6 to divide 9*2, does it follow that 6 divides 2 ?
     
  4. Nov 11, 2012 #3
    But, 6 and 9 are not relatively prime, so we can't use those numbers to test my proof can we?
     
  5. Nov 11, 2012 #4

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    your proof doesn't use relative prime-ness :confused:
     
  6. Nov 11, 2012 #5
    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.
     
  7. Nov 11, 2012 #6

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    this part of your proof is not true (and does not mention relative prime-ness) …
     
  8. Nov 11, 2012 #7
    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?
     
  9. Nov 12, 2012 #8
    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
  10. Nov 12, 2012 #9
    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
  11. Nov 12, 2012 #10
    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
     
  12. Nov 12, 2012 #11
    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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Divisibility Proof
  1. Divisibility proof (Replies: 5)

  2. Divisibility proof. (Replies: 5)

  3. Proof - Divisibility (Replies: 24)

  4. Divisibility Proofs (Replies: 2)

  5. Proof of divisibility (Replies: 3)

Loading...