How I find $\gcd(\frac{a^{2m+1}+1}{a+1}, a+1)$? $$\gcd\left(\frac{a^{2m+1}+1}{a+1}, a+1\right)$$
My answer until this moment is: 
$$
For:  a^{2m+1}+1^{2m+1} = (a + 1)^{m+1} - 2a = (a+1)^m(a+1)-2a
$$ where 
\begin{align}
(a + 1)^{m} = a^{2m}+a^{2m-1}+\cdots+1
\end{align}
So,
\begin{align}
a^{2m+1}+1 = [a^{2m}+a^{2m-1}+\cdots+1](a+1)-2a
\end{align}
But, I don't know how to divide :
\begin{align}
\frac{[a^{2m}+a^{2m-1}+\cdots+1](a+1)-2a}{a+1}
\end{align}
 A: $$
\begin{align}
\frac{a^{2m+1}+1}{a+1}
&=\frac{((a+1)-1)^{2m+1}+1}{a+1}\tag1\\
&=\sum_{k=1}^{2m+1}(-1)^{k-1}\binom{2m+1}{k}(a+1)^{k-1}\tag2\\[6pt]
&\equiv2m+1\pmod{a+1}\tag3
\end{align}
$$
Explanation:
$(1)$: $a=(a+1)-1$
$(2)$: Binomial Theorem and algebra
$(3)$: the $k=1$ term is the only one without a factor of $a+1$  
Therefore,
$$
\gcd\left(\frac{a^{2m+1}+1}{a+1},a+1\right)=\gcd(2m+1,a+1)\tag4
$$
A: Here is one approach. Let $b = a + 1$ so $a = b - 1$. Then, we can apply the binomial theorem to obtain the modular equivalence
$$\begin{align*} \frac{a^{2m + 1} + 1}{a + 1} & = \frac{(b - 1)^{2m + 1} + 1}{b}\\
& = \frac{1}{b} \left(1 + \sum_{k = 0}^{2m + 1} \binom{2m + 1}{k} b^{k}(-1)^{2m + 1 - k} \right)\\
& = \frac{1}{b} \left(1 + (-1) + \sum_{k = 1}^{2m + 1} \binom{2m + 1}{k} b^{k}(-1)^{2m + 1 - k}\right) \\
& = \sum_{k = 1}^{2m + 1} \binom{2m + 1}{k} b^{k - 1}(-1)^{2m + 1 - k} \\
& = \binom{2m + 1}{1}(-1)^{2m} + \sum_{k = 2}^{2m + 1} \binom{2m + 1}{k} b^{k - 1}(-1)^{2m + 1 - k} \\
& \equiv 2m + 1 \pmod{b}.\end{align*}$$
Thus, we have $$\frac{a^{2m + 1} + 1}{a + 1} = p(a + 1) + 2m + 1$$ for an integer $p$. Finally, we can use the fact that $\gcd(x,y) = \gcd(x - ty,y)$ for any integer $t$, to obtain $$\gcd\left( \frac{a^{2m + 1} + 1}{a + 1}, a + 1 \right) = \gcd \left(\frac{a^{2m + 1} + 1}{a + 1} - p(a + 1), a + 1 \right) = \gcd(2m + 1, a + 1).$$
