2017 Is Coming!

Let a a and b b be relatively prime positive integers. Find the sum of all possible values of

gcd ( a 2017 + b 2017 a + b , a + b ) . \gcd \left(\frac{a^{2017} + b^{2017}}{a + b}, \ a + b \right).

Note: 2017 is prime .


The answer is 2018.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Brian Yao
Oct 2, 2016

We denote the greatest common divisor of x x and y y as ( x , y ) (x,y) . I will use the following results:

  1. If ( x , y ) = 1 (x,y) = 1 , then ( x , y z ) = ( x , z ) (x,yz) = (x,z) for positive x , y , z x,y,z .
  2. For any integer t t , ( x , y ) = ( x , y + t x ) (x,y) = (x, y + tx) .

We show now that for any odd prime p p , if a a and b b are relatively prime, ( a p + b p a + b , a + b ) \left(\frac{a^p + b^p}{a + b}, a + b \right) is either p p or 1 1 . Let c = a + b c = a + b , so a = c b a = c - b . Then, using the Binomial Theorem, we have: a p + b p a + b = ( c b ) p + b p c = 1 c ( b p + k = 0 p ( p k ) c k ( b ) p k ) = 1 c ( b p + ( b ) p + c k = 1 p ( p k ) c k 1 ( b ) p k ) = k = 1 p ( p k ) c k 1 ( b ) p k ( p 1 ) ( b ) p 1 p b p 1 ( m o d c ) \begin{aligned} \frac{a^p + b^p}{a + b} & = \frac{(c - b)^p + b^p}{c} \\ & = \frac{1}{c}\left(b^p + \sum_{k = 0}^p \binom{p}{k} c^k(-b)^{p - k} \right) \\ & = \frac{1}{c} \left(b^p + (-b)^p + c \sum_{k = 1}^p \binom{p}{k} c^{k - 1}(-b)^{p - k} \right) \\ & = \sum_{k = 1}^p \binom{p}{k} c^{k - 1}(-b)^{p - k} \\ & \equiv \binom{p}{1}(-b)^{p - 1} \\ & \equiv pb^{p - 1} \pmod{c} \end{aligned} So we can write ( a p + b p ) / ( a + b ) = q c + p b p 1 (a^p + b^p)/(a + b) = qc + pb^{p - 1} for some integer q q . Note then, by result 2: ( a , b ) = ( a + b , b ) = ( c , b ) = 1 ( a p + b p a + b , c ) = ( a p + b p a + b q c , c ) = ( p b p 1 , c ) \begin{aligned} (a,b) & = (a + b,b) = (c,b) = 1 \\ \left(\frac{a^p + b^p}{a + b}, c \right) & = \left(\frac{a^p + b^p}{a + b} - qc, c \right) = (pb^{p - 1}, c) \end{aligned} Since ( c , b ) = 1 (c,b) = 1 , ( c , b p 1 ) = 1 (c, b^{p - 1}) = 1 since raising b b to a power does not change its distinct prime factors. Therefore, by result 1: ( a p + b p a + b , c ) = ( p b p 1 , c ) = ( p , c ) \left(\frac{a^p + b^p}{a + b}, c \right) = (pb^{p - 1}, c) = (p,c) If p c p \mid c , then we have ( p , c ) = p (p,c) = p . Otherwise, if p c p \nmid c , since p p is prime, c c and p p are relatively prime, so ( p , c ) = 1 (p,c) = 1 . Therefore, the greatest common divisor of ( a p + b p ) / ( a + b ) (a^p + b^p)/(a + b) and a + b a + b is either p p or 1 1 .

Since we have p = 2017 p = 2017 , our desired sum is p + 1 = 2017 + 1 = 2018 p + 1 = 2017 + 1 = \boxed{2018} .

Edit: As Mark has shown, it is important to show that the case p c p \mid c is possible! Since p p is an odd prime, we can write p = 2 m + 1 = m + ( m + 1 ) p = 2m + 1 = m + (m + 1) where m 1 m \geq 1 is an integer. Since m m and m + 1 m + 1 are relatively prime (suppose they aren't; then they have a common divisor d > 1 d > 1 such that d 1 = ( m + 1 ) m d \mid 1 = (m + 1) - m , a contradiction), by letting a = m a = m and b = m + 1 b = m + 1 , we have c = 2 m + 1 = p c = 2m + 1 = p , which leads us to p c p \mid c . By a similar argument, p c p \nmid c is possible by taking an odd prime c p c \neq p .

Mark Hennings
Oct 5, 2016

Note that F ( a , b ) = a 2017 + b 2017 a + b = j = 0 2016 ( 1 ) j a 2016 j b j F(a,b) \; = \; \frac{a^{2017} + b^{2017}}{a+b} \; = \; \sum_{j=0}^{2016} (-1)^j a^{2016-j} b^j Regarding F ( a , b ) F(a,b) as a polynomial in a a with integer coefficients, the Remainder Theorem tells us that F ( a , b ) = ( a + b ) G ( a ) + F ( b , b ) F(a,b) \; = \; (a+b)G(a) + F(-b,b) for some polynomial G ( a ) G(a) with integer coefficients. Thus the HCF of F ( a , b ) F(a,b) and a + b a+b is also the HCF of F ( b , b ) = 2017 b 2016 F(-b,b) = 2017b^{2016} and a + b a+b . Since a , b a,b are coprime, no divisor of a + b a+b can have a prime factor in common with b b , and hence it follows that the only possible HCFs of F ( a , b ) F(a,b) and a + b a+b are 1 1 and 2017 2017 . Putting a = 1009 a=1009 , b = 1008 b=1008 shows that we can obtain 2017 2017 as HCF. Putting a = 2 a=2 , b = 3 b=3 shows that we can obtain 1 1 as HCF. This makes the answer 1 + 2017 = 2018 1+2017 = \boxed{2018} .

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...