2017 Is Coming!

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

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

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

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