1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Largest GCD of consequtive elements in a sequence.

  1. Sep 18, 2010 #1
    Say I have a sequence a(n) = 100 + n^2 with n ranging through the positive integers. I want to find the largest number g(n) such that g(n) = gcd(a(n), a(n+1)).

    Let g be a number that divides both a(n) and a(n+1)
    g | 100 + n^2 and g | 100 + n^2 + 2n + 1 therefore g | 2n + 1. This means that g must be an odd number since it divides another odd number.

    g | 100 + n^2 so g | 100(1 + (n^2)/100) -> g | 100 or g | 1 + (n/10)^2
    if g | 100 then g | n^2 which means that n is a multiple of 5 since the only odd divisors of 100 are 5, 25 and 1 with 1 being trivial. This cannot be the case since g must also divide 2n + 1. Therefore g | 1 + (n/10)^2 which implies that n is a multiple of 10 since 1 + (n/10)^2 must be an integer. Let n = 10k.

    So now we have
    g | k^2 + 1 and g | 20k + 1

    I have no idea how to proceed from this point. In fact I'm not even sure that I'm on the right track. If anyone can show me how to proceed from this point, or even if they have a completely alternate solution I'd much appreciate it. I am not used to these kinds of problems so please be as thorough as possible otherwise I will have trouble keeping up.
     
  2. jcsd
  3. Sep 18, 2010 #2
    (1) This would true only if g were a prime or, at least, relatively prime to one of the factors.

    (2) 1 + (n/10)^2 how can you be sure that this number is an integer?
     
  4. Sep 18, 2010 #3
    I'm not sure what is meant by 1, I have studied very minimal number theory.

    What I'm attempted to do was show that if g doesn't divide into 100, then it must divide into (1+(n/10)^2). Since g cannot be 100 + n^2 which is larger than 2n+1, it must be one of the factors which in themselves must be integers. I must divide the term by a perfect square x^2 for 100/x^2 + (n/x)^2 to have a chance of being an integer. The only perfect squares that divide 100 are 4, 25 and 100 itself. I think I could have picked any of these 3 but I figured 100 would be easiest to work with.

    I assumed that 1 + (n/10)^2 must be an integer since g divides it, is that wrong?
     
  5. Sep 18, 2010 #4
    As you cannot assume that g divides it, yes.
     
  6. Sep 18, 2010 #5
    Well, I'm lost then. Can anyone show me the solution to this problem?
     
  7. Sep 19, 2010 #6

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Where is this question from? Why do you believe there is a closed-form simplification for the gcd?
     
  8. Sep 19, 2010 #7
    It's from the 2009 Small C Contest at University of Waterloo. They have given an answer to the problem actually, but not a solution. I'm curious to see how it's solved.
     
  9. Sep 19, 2010 #8
    I think that I found the problems from the 2009 Small c Contest on the web. I'll post the relevant question here. It helps that the problem was multiple choice; that makes the solution easier.

    The numbers 101, 104, 109, 116, 125, ... are of the form an = 100+n2, where n = 1, 2, 3, 4, 5, ... . For each n, let dn be the greatest common divisor of an and an+1. What is the maximum value of dn, as n ranges through the positive integers?

    (A) 521 (B) 611 (C) 901 (D) 401 (E) 101


    I'll spoiler my solution, in case anyone else wants to solve it:

    The answer is (D) 401. We first note that

    2002 + 100 = (401)(100)
    2012 + 100 = (401)(101)

    so 401 is a possible solution. We need to rule out the choices of 901, 611 and 521 to conclude that (D) is the solution.

    901: If there exists an n such that 901 divides both n2 + 100 and (n+1)2 + 100, then 901 divides the difference 2n + 1. Hence there exists an odd number 2m + 1 such that 901(2m + 1) = 2n +1. Solving for n,

    n = 901m + 450

    and so

    n2 + 100 = 9012m2 + 2(901)(450)m + 202,600.

    But 202,600 isn't divisible by 901 so n2 + 100 can't be divisible by 901.

    The cases of 611 and 521 are also ruled out by similar reasoning. Therefore, the answer is (D) 401.
     
    Last edited: Sep 19, 2010
  10. Sep 19, 2010 #9
    I was aware that the question was multiple choice and I know a solution if I were given the choices in the test. But I wanted to see if there was a way of solving the problem without being given any of the choices. Thanks for your solution nonetheless.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Largest GCD of consequtive elements in a sequence.
  1. What is gcd? (Replies: 3)

  2. GCD of polynomials? (Replies: 4)

  3. Largest Known Prime (Replies: 20)

  4. Gcd(a,b) = gcd(a,b+a) (Replies: 4)

Loading...