<s>[INST] Prove the following conditional divisibility If $gcd(a,b)=1$ and $n$ is a prime number,then prove that $\frac{(a^n + b^n)}{(a+b)}$ and $(a+b)$ have no factors in common unless $(a+b)$ is a multiple of $n$.
I don't know how to establish the relation between $n$ and $(a+b)$. This is how much I have been able to derive :
$${\frac{(a^n+b^n)}{(a+b)}=(a+b)^{n-1} + \frac{C_1a^{n-1}b +C_2a^{n-2}b^2+...+C_{n-1}ab^{n-1}}{(a+b)}}$$
We need to prove that,$${gcd((a+b)^{n-1}+\frac{C_1a^{n-1}b +C_2a^{n-2}b^2+...+C_{n-1}ab^{n-1}}{(a+b)},(a+b))=1}$$ unless $n=s.(a+b)$ for some $s$.
I have no idea how to proceed. Please help. Thank you! :)
 [/INST] Because $n$ is odd (note: for $n=2$, $\frac{a^2+b^2}{a+b}$ need not be an integer) we have $$a^n+b^n=(a+b)(a^{n-1}-a^{n-2}b+a^{n-3}b^2-a^{n-4}b^3+\cdots-a^1b^{n-2}+b^{n-1})$$
We compute $$gcd(a^{n-1}-a^{n-2}b+a^{n-3}b^2-a^{n-4}b^3+\cdots-a^1b^{n-2}+b^{n-1},a+b)=$$
$$gcd(a^{n-1}-a^{n-2}b+a^{n-3}b^2-a^{n-4}b^3+\cdots-a^1b^{n-2}+b^{n-1}\color{red}{-a^{n-2}(a+b)},a+b)=$$
$$gcd(-2a^{n-2}b+a^{n-3}b^2-a^{n-4}b^3+\cdots-a^1b^{n-2}+b^{n-1}\color{red}{+2a^{n-3}(a+b)},a+b)=$$
$$gcd(3a^{n-3}b^2-a^{n-4}b^3+\cdots-a^1b^{n-2}+b^{n-1}\color{red}{-3a^{n-4}(a+b)},a+b)=$$
$$\cdots$$
$$=gcd(nb^{n-1},a+b)$$
However, since $gcd(a,b)=1$, also $1=gcd(a+b,b)=gcd(a+b,b^{n-1})$.  Hence we can reduce the original to $gcd(n,a+b)$.  Since $n$ is prime this is either $1$ or $n$.
</s>