Largest GCD of consequtive elements in a sequence.

[Yuqing]

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.

 

[JSuarez]

g | 100(1 + (n^2)/100) -> g | 100 or g | 1 + (n/10)^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?

 

[Yuqing]

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?

 

[JSuarez]

I assumed that 1 + (n/10)^2 must be an integer since g divides it, is that wrong?

As you cannot assume that g divides it, yes.

 

[Yuqing]

Well, I'm lost then. Can anyone show me the solution to this problem?

 

[Gokul43201]

Where is this question from? Why do you believe there is a closed-form simplification for the gcd?

 

[Yuqing]

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.

 

[Petek]

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 a_n = 100+n², where n = 1, 2, 3, 4, 5, ... . For each n, let d_n be the greatest common divisor of a_n and a_n+1. What is the maximum value of d_n, 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:

Spoiler

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

200² + 100 = (401)(100)
201² + 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 n² + 100 and (n+1)² + 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

n² + 100 = 901²m² + 2(901)(450)m + 202,600.

But 202,600 isn't divisible by 901 so n² + 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.

 

[Yuqing]

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.