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

$\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.

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

We show now that for any odd prime $p$ , if $a$ and $b$ are relatively prime, $\left(\frac{a^p + b^p}{a + b}, a + b \right)$ is either $p$ or $1$ . Let $c = a + b$ , so $a = c - b$ . Then, using the Binomial Theorem, we have: $\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) = qc + pb^{p - 1}$ for some integer $q$ . Note then, by result 2: $\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^{p - 1}) = 1$ since raising $b$ to a power does not change its distinct prime factors. Therefore, by result 1: $\left(\frac{a^p + b^p}{a + b}, c \right) = (pb^{p - 1}, c) = (p,c)$ If $p \mid c$ , then we have $(p,c) = p$ . Otherwise, if $p \nmid c$ , since $p$ is prime, $c$ and $p$ are relatively prime, so $(p,c) = 1$ . Therefore, the greatest common divisor of $(a^p + b^p)/(a + b)$ and $a + b$ is either $p$ or $1$ .

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

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