Results 1 to 2 of 2

Math Help - Highest common factor proof

  1. #1
    Newbie
    Joined
    Oct 2012
    From
    london
    Posts
    2

    Highest common factor proof

    Ive got the question: "For non-zero intergers a, m and n, prove that if a is a factor of mn, then a is also a factor of hcf(a,m) x hcf(a,n)"

    I've been told to use integral linear combination but I don't see how that is relevent??

    Any help at all would be much appreciated
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Oct 2012
    From
    london
    Posts
    2

    Re: Highest common factor proof

    Nevermind I've worked it out,

    If anyone is interested:

    Suppose mn/a. Then there exists an interger q such that mn=qa. Using linear combinations we get hcf(a,m)=ra+sm for some intergers r and s, and hcf(a,n)=ta+bn for some intergers t and b.

    Therefore:

    Hcf(a,m) x hcf(a,n) = (ra+sm)(ta+bn)
    =rt(a^2)+rabn+smta+smnb
    =rt(a^2)+rabn+smta+sqab using (mn=qa) from above
    =a(rta+rbn+smt+sqb)

    So that (hcf(a,m)xhcf(a,n))/a
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: January 25th 2011, 04:38 AM
  2. Highest common factor, Polynomial division
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: January 22nd 2010, 08:58 AM
  3. Highest Common Factor help
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 27th 2009, 01:37 AM
  4. Replies: 2
    Last Post: March 14th 2009, 03:56 AM
  5. Highest Common Factor using Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: August 29th 2007, 04:28 PM

Search Tags


/mathhelpforum @mathhelpforum