on $p^n+q^n=(p+q)^k$ Evaluate the condition for integer solutions for $n$.
I found this question in an old book:
Find smallest number of form $2^n+3^n$ divisible by $625$. This solution is from that book; n must be odd and we may write:
$$2^n+3^n$$ $$=2^n+(-1)^n(2-5)^n$$ $$=2^n+(-1)^n\cdot 2^n-(-1)^n\cdot2^{n-1}\cdot5\cdot n+(-1)^n\cdot2^{n-2}\cdot5^2\frac{n(n-1)}{2}-(-1)^n\cdot2^{n-3}\cdot5^3\frac{n(n-1)(n-2)}{6}+625 N$$
$$2^n+3^n=5n\big[2^{n-1}-(n-1)2^{n-2}.5+\frac{(n-1)(n-2)}{3}2^{n-2}.5^2\big]+625 N;\ n\geq 4$$
The value inside box bracket is not divisible by $5$, so $n$ must be divisible by $125$ if $2^n+3^n$ must be divisible by $625$.
Similar reasoning can be used for any primes $p$ and $q$ such that:
$p^n+q^n≡0 \ mod (p+q)^k$
The condition is 
 $n=(p+q)^{k-1}$.
Now we try to apply Euler $\phi$ function:
$\phi(625)=625\big(1-\frac{1}{5}\big)=500$
$2^{500}≡1 \mod 625$
$3^{500}≡ 1 \ mod 625$
$3^{500}-2^{500}≡0 \mod 625$
$(3^{125}-2^{125})(3^{125}+2^{125})(3^{250}+2^{250})≡0 \mod 625$
Only $3^{125}+2^{125}$ can be divisible by 625. But $3^{125}+2^{125}$ can be factorized more and more.Suppose we can not use first method because p and q are too large, then how can we be sure the smaller factors are not divisible by $625$? is $n=125$ the smallest number?

A GENERAL PROOF
If $p$ and $q$ are distinct primes then $p,q,p,p+q$ are pairwise coprime. 
We require $n$ to be odd and then $$\frac{p^n+q^n}{p+q}=p^{n-1}-qp^{n-2}+ ... +q^{n}\equiv np^{n-1}\pmod {p+q}$$
Therefore $p^n+q^n$ is divisible by $(p+q)^{k}$ if and only if $n$ is divisible by $(p+q)^{k-1}$.
