Number TheoryhardFree

GCD of Terms in 101,104,109,116... Sequence | IOQM

JEE Maths question with a full step-by-step solution.

Question
The numbers in the sequence 101, 104, 109, 116, …101,\,104,\,109,\,116,\,\ldots are of the form an=100+n2a_n=100+n^2, where n=1,2,3,…n=1,2,3,\ldots. For each nn, let dnd_n be the greatest common divisor of ana_n and an+1a_{n+1}. Let kk be the maximum value of dnd_n as nn ranges over the positive integers. Find the value of k−120\dfrac{k-1}{20}.
Solution
Answer: 20
Step 1: Write out the two consecutive terms. Since an=100+n2a_n=100+n^2,
an+1=100+(n+1)2=101+2n+n2,a_{n+1}=100+(n+1)^2=101+2n+n^2,
 so we need dn=gcd⁡(100+n2, 101+2n+n2)d_n=\gcd\big(100+n^2,\ 101+2n+n^2\big). Step 2: Note the parity. Their difference is an+1−an=2n+1a_{n+1}-a_n=2n+1, which is odd. So one of an, an+1a_n,\,a_{n+1} is odd and the other is even, which means their common divisor cannot be even:
dn=gcd⁡(an,an+1)≠even.d_n=\gcd(a_n,a_{n+1})\neq\text{even}.
 Step 3: Reduce using the difference. A common divisor of ana_n and an+1a_{n+1} also divides an+1−an=2n+1a_{n+1}-a_n=2n+1, so
dn=gcd⁡(an, 2n+1).d_n=\gcd(a_n,\,2n+1).
 Because dnd_n is odd, multiplying ana_n by 44 does not change the gcd (as 44 shares no odd factor):
dn=gcd⁡(4an, 2n+1)=gcd⁡(400+4n2, 2n+1).d_n=\gcd\big(4a_n,\ 2n+1\big)=\gcd\big(400+4n^2,\ 2n+1\big).
 Step 4: Eliminate the n2n^2 term. Using the identity (2n+1)(2n−1)=4n2−1(2n+1)(2n-1)=4n^2-1, subtract a multiple of 2n+12n+1 from 400+4n2400+4n^2:
400+4n2−(2n+1)(2n−1)=400+4n2−(4n2−1)=401.400+4n^2-(2n+1)(2n-1)=400+4n^2-(4n^2-1)=401.
 Therefore
dn=gcd⁡(401, 2n+1).d_n=\gcd\big(401,\ 2n+1\big).
 Step 5: Find the maximum. The number 401401 is prime, so gcd⁡(401, 2n+1)\gcd(401,\,2n+1) is either 11 or 401401. Its largest value is 401401, attained whenever 2n+12n+1 is a multiple of 401401 (for example 2n+1=4012n+1=401, i.e. n=200n=200). Hence
k=max⁡ndn=401.k=\max_n d_n=401.
 Step 6: Compute the required value:
k−120=401−120=40020=20.\frac{k-1}{20}=\frac{401-1}{20}=\frac{400}{20}=20.
 Answer: 20
Still stuck on this question?Ask your doubt on WhatsApp
Similar questions
Number Theory · medium
The function f is defined on the set of integers and satisfies f(n)= cases n-3, if n≥1000…
Number Theory · hard
How many of the numbers 1², 2², 3², …, 1999² have an odd digit in the tens place?
Number Theory · medium
Let N=2222^(5555)+5555^(2222) . Let r be the remainder when N is divided by 462 . Find th…

Solve more, learn faster

Sign up free to solve more JEE Maths questions and explore doMath — timed drills, mastery sprints, bookmarks, and chapter-wise progress tracking.

Sign up freeExplore doMath