Largest GCD of consequtive elements in a sequence.

In summary, the conversation discusses a problem from the 2009 Small C Contest at University of Waterloo about finding the largest possible value of the greatest common divisor of a sequence of numbers. The sequence is given by a(n) = 100 + n^2 with n ranging through the positive integers. The solution is found by considering the factors of 100 and using the fact that the greatest common divisor must divide into 2n + 1. The conversation also includes a discussion about whether or not there is a closed-form simplification for the greatest common divisor.
  • #1
Yuqing
218
0
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.
 
Mathematics news on Phys.org
  • #2
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?
 
  • #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?
 
  • #4
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.
 
  • #5
Well, I'm lost then. Can anyone show me the solution to this problem?
 
  • #6
Where is this question from? Why do you believe there is a closed-form simplification for the gcd?
 
  • #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.
 
  • #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:
  • #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.
 

1. What is the largest GCD of consecutive elements in a sequence?

The largest GCD of consecutive elements in a sequence is the greatest common divisor of the largest pair of consecutive numbers in the sequence. It is the largest number that can divide both of the consecutive numbers without leaving a remainder.

2. How is the largest GCD of consecutive elements in a sequence calculated?

The largest GCD of consecutive elements in a sequence can be calculated by finding the GCD of each pair of consecutive numbers in the sequence and then comparing them to determine the largest GCD.

3. What is the significance of finding the largest GCD of consecutive elements in a sequence?

Finding the largest GCD of consecutive elements in a sequence can help us understand the common factors shared by consecutive numbers in a sequence. This can be useful in identifying patterns and relationships within the sequence.

4. Can the largest GCD of consecutive elements in a sequence be greater than 1?

Yes, the largest GCD of consecutive elements in a sequence can be greater than 1. In fact, if the sequence contains only prime numbers, the largest GCD will be 1 as there are no common factors between consecutive prime numbers.

5. How is the largest GCD of consecutive elements in a sequence used in real-world applications?

The concept of GCD and the largest GCD of consecutive elements in a sequence is used in various fields such as cryptography, number theory, and computer science. It is also used in music theory to determine the common factors between musical intervals and chords.

Similar threads

Replies
14
Views
1K
  • General Math
Replies
8
Views
1K
Replies
5
Views
850
Replies
5
Views
2K
  • General Math
Replies
2
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
704
  • Calculus and Beyond Homework Help
Replies
1
Views
449
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
532
Replies
4
Views
892
Back
Top