Results 1 to 5 of 5

Math Help - elem. # theo - gcd(a, a+n) divides n ...

  1. #1
    Member cassiopeia1289's Avatar
    Joined
    Aug 2007
    From
    chicago
    Posts
    101

    elem. # theo - gcd(a, a+n) divides n ...

    OK: "Prove that, for a positive integer n and any integer a, gcd(a, a+n) divides n; hence, gcd(a, a+1) = 1."

    starters: "HENCE"??? is that essentially the "therefore, by the given gcd(a, a+n) divides n, then gcd(a, a+1) must equal 1"???
    Or are we supposed to prove the gcd(a, a+n) part?

    Either way, where do I start?
    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 cassiopeia1289 View Post
    OK: "Prove that, for a positive integer n and any integer a, gcd(a, a+n) divides n; hence, gcd(a, a+1) = 1."
    Let d=\gcd(a,a+n). Therefore, d|a and d|(a+n). Therefore, d|[(a+n) - a] \implies d|n.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member cassiopeia1289's Avatar
    Joined
    Aug 2007
    From
    chicago
    Posts
    101
    Ok, yeah thanks but didn't really answer my question.
    Are we trying to prove gcd(a, a+1) = 1 as the end result?
    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 cassiopeia1289 View Post
    Ok, yeah thanks but didn't really answer my question.
    Are we trying to prove gcd(a, a+1) = 1 as the end result?
    That does answer your question. Because if d=\gcd(a,a+1) then d|1 \implies d= 1 (by above).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member cassiopeia1289's Avatar
    Joined
    Aug 2007
    From
    chicago
    Posts
    101
    ah ok, so the answer would be: yes! it is asking you to prove that gcd(a,a+1)=1!
    (sorry, its just, I didn't really want like the whole think figured out for me, I wanted to learn and do the work, but needed just a little nudge in the right direction as to what the question is actually asking and where to start - but still thanks, though)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. elem#theo - phi and odd #
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: December 2nd 2008, 07:45 PM
  2. elem#theo - induction + Bertrand's
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: October 23rd 2008, 05:04 PM
  3. elem.num.theo - diophantine equations
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: October 9th 2008, 03:23 PM
  4. elem.num.theo - GCD
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: October 9th 2008, 02:23 PM
  5. elem.num.theo - help w/proof
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 26th 2008, 07:18 AM

Search Tags


/mathhelpforum @mathhelpforum