Results 1 to 6 of 6

Math Help - HCF and Dividing Numbers

  1. #1
    Junior Member
    Joined
    Oct 2007
    From
    Bath, UK
    Posts
    25

    HCF and Dividing Numbers

    Prove that xa+yb=c has integer solution x, y iff hcf(a,b)|c.
    I have to prove this both ways, because of the iff statement. So first, I let d = hcf(a,b) and assume it divides c, to show that xa+yb=c has integer solutions.

    1) xy + yb = c
    2) (xa)/d + (yb)/d = c/d
    3) x(a/d) + y(b/d) = c/d
    4) By the definition of the HCF, d|a, d|b, so a/d, b/d are integers. If c/d (by assumption) is an integer too, there will be integers x, y that satisfy the above equasion.

    Now, I have to assume that xa+yb=c has integer solutions, and then show that d|c to finish the proof, but I dont know where to start, does anyone have any suggestions?

    1) ???

    Prove that hcf(na,nb) = n*hcf(a,b) for a, b, n integers, and n > 0
    I've attempted the above problem, and been advised to prove that both sides of the equasion divide the other, and hence, they're both equal. However, I've hit at some contradictions, and I'd like to know where I'm going wrong.

    1) Let c = hcf(na,nb), and d = n*hcf(a,b). Note that n|d.
    2) Note that c|na, c|nb and thus, c|n.
    3) c|n and n|d => c|d.
    4) Now, consider c/d = c/n * c/hcf(a,b).

    Now, I want to show that both of those are integers, thus making c/d an integer, thus showing that d|c and proving the statement. But, I can't seem to show how. Can anyone help me with my proof?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1
    Quote Originally Posted by bumcheekcity View Post
    I have to prove this both ways, because of the iff statement. So first, I let d = hcf(a,b) and assume it divides c, to show that xa+yb=c has integer solutions.

    1) xy + yb = c
    2) (xa)/d + (yb)/d = c/d
    3) x(a/d) + y(b/d) = c/d
    4) By the definition of the HCF, d|a, d|b, so a/d, b/d are integers. If c/d (by assumption) is an integer too, there will be integers x, y that satisfy the above equasion.

    Now, I have to assume that xa+yb=c has integer solutions, and then show that d|c to finish the proof, but I dont know where to start, does anyone have any suggestions?

    1) ???



    I've attempted the above problem, and been advised to prove that both sides of the equasion divide the other, and hence, they're both equal. However, I've hit at some contradictions, and I'd like to know where I'm going wrong.

    1) Let c = hcf(na,nb), and d = n*hcf(a,b). Note that n|d.
    2) Note that c|na, c|nb and thus, c|n.
    3) c|n and n|d => c|d.
    4) Now, consider c/d = c/n * c/hcf(a,b).

    Now, I want to show that both of those are integers, thus making c/d an integer, thus showing that d|c and proving the statement. But, I can't seem to show how. Can anyone help me with my proof?
    I assume hcf = highest common factor (I learned it as greatest common divisor).

    This isn't a proof, just the method I would use to approach it.

    Consider n divides na, and na can be broken down into a prime factorization.
    And n divides nb, and nb can be broken down into a prime factorization.

    And the highest common factor of two numbers in their prime factorization form is the lowest value of the exponent of each prime factor

    So, for example, if a = 20, then it's prime factorization is 2^{2}\cdot 5 and if b = 25 then it's prime factorization is 5^{2} and so the highest common factor is
    2^{min(2,0)}\cdot 5^{min(1,2)} = 2^{0}\cdot 5^{1} = 5

    Now, if you multiply both numbers by an integer n, then the prime factorization of n will be in both numbers prime factorization, and will consequently be in the answer for the hcf(na, nb) which means that n divides hcf(na, nb). and n * hcf(a,b) = hcf(na,nb)

    So like lets say our last problem we chose n=15, then na=15*20=300, and the prime factorization of na is
    2^{2}\cdot 3\cdot 5^{2} and nb = 15*25=375 then it's prime factorization is 3\cdot 5^{3} and so the highest common factor is
    2^{min(2,0)}\cdot 3^{min(1,1)}{\cdot 5^{min(2,3)} = 2^{0}\cdot 3^{1} 5^{2} = 75

    and 15 divides 75, leaving 5 leftover. \frac{hcf(na,nb)}{n} = hcf(a,b)

    I hope that made sense, I'm really bad at writing proofs, so I just wanted to give you an example of what method I think would be easiest to show it.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor kalagota's Avatar
    Joined
    Oct 2007
    From
    Taguig City, Philippines
    Posts
    1,026
    Prove that hcf(na,nb) = n*hcf(a,b) for a, b, n integers, and n > 0
    ----------------------------------------------

    let d=hcf(na,nb). then 1 = hcf \left( {\frac{na}{d},\frac{nb}{d}}\right) = hcf \left( {\frac{n}{d}a,\frac{n}{d}b}\right)

    \implies \frac{d}{n} = hcf(a,b)
    \implies hcf(na,nb) = n*hcf(a,b)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Let a,b\in \mathbb{Z}^+ and suppose that ax+by=c has a solution in x,y\in \mathbb{Z} for c\in \mathbb{Z}^+. Then \gcd(a,b) = d divides the LHS and so it must divide the RHS i.e. d|c. Now we need to prove the converse, since d=\gcd(a,b) we can write ax'+by' = d for x',y'\in \mathbb{Z} since d|c\implies c=dk so a(x'k)+b(y'k) = dk = c and so x'k,y'k are solutions. Q.E.D.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2007
    From
    Bath, UK
    Posts
    25
    Quote Originally Posted by kalagota View Post
    Prove that hcf(na,nb) = n*hcf(a,b) for a, b, n integers, and n > 0
    ----------------------------------------------

    let d=hcf(na,nb). then 1 = hcf \left( {\frac{na}{d},\frac{nb}{d}}\right) = hcf \left( {\frac{n}{d}a,\frac{n}{d}b}\right)

    \implies \frac{d}{n} = hcf(a,b)
    \implies hcf(na,nb) = n*hcf(a,b)
    Thankyou all very much for your help. But I have a quick question. The logical step inbetween line 1 and line 2 of this proof means you take a 'factor' of n/d out of the HCF. But this is what we are trying to prove, surely? We are trying to prove that hcf(na,nb) = n*hcf(a,b), and taking the factor of n out of the HCF is assuming the solution to prove the solution, or am I missing a step?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor kalagota's Avatar
    Joined
    Oct 2007
    From
    Taguig City, Philippines
    Posts
    1,026
    indeed, there was a missing step (i thought it can easily be seen or i has been proven already)

    okay, here it is.. (if hcf is just equivalent to gcd..)
    if d=gcd(na,nb), then d = rna + snb for some r,s integers which implies that 1 = \frac{rna}{d} + \frac{snb}{d}
    \implies 1 = \frac{n}{d}ra + \frac{n}{d}sb
    \implies \frac{d}{n} = ra + sb
    whether \frac {d}{n} an integer or not, it can be assume that \frac{d}{n} = gcd(a,b) \implies d=n*gcd(a,b)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Dividing mixed numbers and fractions.
    Posted in the Algebra Forum
    Replies: 3
    Last Post: May 22nd 2011, 04:56 PM
  2. dividing complex numbers
    Posted in the Algebra Forum
    Replies: 2
    Last Post: April 20th 2011, 11:17 PM
  3. dividing large numbers
    Posted in the Algebra Forum
    Replies: 3
    Last Post: May 9th 2010, 02:30 AM
  4. Dividing Complex Numbers
    Posted in the Algebra Forum
    Replies: 1
    Last Post: November 4th 2008, 09:33 PM
  5. Dividing real numbers
    Posted in the Algebra Forum
    Replies: 1
    Last Post: January 23rd 2007, 05:38 AM

Search Tags


/mathhelpforum @mathhelpforum