Results 1 to 8 of 8

Math Help - greatest common factors

  1. #1
    Newbie
    Joined
    Mar 2008
    Posts
    7

    greatest common factors

    I'm stuck on this:

    For all positive integers n and all integers a, gcf(a, a+n) | n.
    (For all positive integers n and all integers a, the greatest common fact of 'a' and 'a+n' divides into 'n').

    Anybody know where to start?
    Last edited by pizzaRusher1234; March 12th 2008 at 03:21 PM. Reason: a little confusion, maybe?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by pizzaRusher1234 View Post
    I'm stuck on this:

    For all positive integers n and all integers a, gcf(a, a+n) | n.
    (For all positive integers n and all integers a, the greatest common fact of 'a' and 'a+n' divides into 'n').

    Anybody know where to start?
    For positive integers this statement is always true. Let d=gcd(a,a+n) then d|a and d|(a+n) so d|n. Thus, gcd(a,a+n) |n.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2008
    Posts
    7
    Quote Originally Posted by ThePerfectHacker View Post
    For positive integers this statement is always true. Let d=gcd(a,a+n) then d|a and d|(a+n) so d|n. Thus, gcd(a,a+n) |n.
    how do you know that d divides a+n? Is there a proof?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by pizzaRusher1234 View Post
    how do you know that d divides a+n? Is there a proof?
    If d=gcd(a,a+n) then by definition d|a and d|(a+n).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Mar 2008
    Posts
    7
    sorry.

    you said "[since] d|a and d|(a+n) [then] d|n"

    I meant how do you know that d|n? Is there a proof for that?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,

    In a general case, if d|a and d|b, d|ax+by, \forall x,y \in \mathbb{Z}^2

    So if d|a and d|(a+n), d|a+n-a=n

    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Mar 2008
    Posts
    7
    Quote Originally Posted by Moo View Post
    Hello,

    In a general case, if d|a and d|b, d|ax+by, \forall x,y \in \mathbb{Z}^2

    So if d|a and d|(a+n), d|a+n-a=n

    is this sort of like this

    for integers a,b,c: c = ax + by if, and only if, gcf(a, b)|c.


    How would a proof of that go?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    The "if and only if" is correct, but it's not a real definition ;-)

    You can say "if c=ax+by, SO gcf(a,b) divides c"

    Let's write it :-)

    If d=gcf(a,b), then a=da' and b=db' (with a' and b' coprime, but it doesn't matter for the demonstration)

    So c=da'x+b'dy=d(a'x+b'y)

    So d divides c, it's as simple as this ^^
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Greatest Common Divisor of (9m+8, 6m+5)
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 15th 2011, 06:43 AM
  2. [SOLVED] Least common multiple - Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: October 25th 2010, 06:45 AM
  3. greatest and least common factor
    Posted in the Algebra Forum
    Replies: 3
    Last Post: September 3rd 2010, 03:21 PM
  4. Greatest Common Divisor.
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 23rd 2009, 01:36 AM
  5. Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 4th 2008, 02:08 AM

Search Tags


/mathhelpforum @mathhelpforum