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
    9
    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
    9
    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, 06:45 PM
  2. elem#theo - induction + Bertrand's
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: October 23rd 2008, 04:04 PM
  3. elem.num.theo - diophantine equations
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: October 9th 2008, 02:23 PM
  4. elem.num.theo - GCD
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: October 9th 2008, 01:23 PM
  5. elem.num.theo - help w/proof
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 26th 2008, 06:18 AM

Search Tags


/mathhelpforum @mathhelpforum