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 ff is defined on the set of integers and satisfies f(n)={n−3,if n≥1000,f(n+5),if n<1000.f(n)=\begin{cases}n-3, & \text{if } n\ge1000,\\[2pt] f(n+5), & \text{if } n<1000.\end{cases} Find the sum of the prime factors of f(84)f(84).
Number Theory · hard
How many of the numbers 12,22,32,…,199921^2, 2^2, 3^2, \ldots, 1999^2 have an odd digit in the tens place?
Number Theory · medium
Let N=22225555+55552222N=2222^{5555}+5555^{2222}. Let rr be the remainder when NN is divided by 462462. Find the sum of the distinct prime factors of rr.
Number Theory · medium
If x1,x2,x3,x4,x5x_1,x_2,x_3,x_4,x_5 are five consecutive natural numbers with x1+x2+x3+x4+x5=n3andx2+x3+x4=m2,x_1+x_2+x_3+x_4+x_5 = n^3 \qquad\text{and}\qquad x_2+x_3+x_4 = m^2 , where mm and nn are natural numbers, then the least possible value of n3+m22\dfrac{n^3+m^2}2

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