Solution:

Contributions came from Farideh Firoozbakht and Ken Wilke.

Faride wrote:

" If p is an odd prime and x & y are integers such that x+y !=0 and gcd(x, y)=gcd(p, x+y)=1 then all prime divisors of, (x^p+y^p)/(x+y) are of the for 2*k*p+1." (I)

For the proof of (I), I use from the following lemma.

Lemma : For Integers x and y and natural numbers m & n , gcd(x^m+y^m, x^n+y^n) =|x^gcd(m, n)+y^gcd(m, n)|

Proof of (I) : Let m = (x^p+y^p)/(x+y) and q be a prime divisor of m, so q is a prime divisor of x^p+y^p.

We know q doesn't divide x and q doesn't divide y because if q divides one of the x & y since q divides x^p + y^p , then q divides the other one, but this is a contradiction with the gcd (x, y) = 1. q doesn't divide x and since q is prime hence gcd (q, x) = 1 , then there exists a number t such t*x = 1 (mod q), we also know q divides x^p+y^p so q divides t^p(x^p+y^p) hence q divides (t*y)^p+1, so, q divides (t*y)^(2p)-1 (I.1) and since q doesn't divide t*y , by Fermat theorem q divides (t*y)^(q-1)-1 (I.2) so from (I.1) & (I.2) we have , q divides gcd((t*y)^(2p)-1, (t*y)^(q-1)-1) hence by using lemma , q divides (t*y)^gcd(2p, q-1)-1, since 2p & q-1 are even numbers and p is prime ,gcd (2p, q-1) = 2 or 2 p, If we show that the first case doesn't happen, then gcd (2p, q-1) = 2p so q is of the form 2*k*p + 1. gcd (2p, q-1) != 2 , because if gcd(2p, q-1) = 2 since q divides (t*y)^gcd(2p, q-1)-1 then, q divides (t*y)^2-1 (I.3) we also know q divides (t*x)-1 so , q divides ( t*x)^2-1 (I.4) and from (I.3) & (I.4) we have , q divides t^2(x^2-y^2) , but q doesn't divide t so q divides x^2-y^2 hence q divides x - y or q divides x + y, we show that these two cases can not be happen.

case 1 : If q divides x - y , then q divides x^p - y^p and since q divides x^p + y^p , so q divides 2x^p and q divides 2 y^p , hence q divides x & y , but this is a contradiction because gcd (x, y) = 1.

case 2 : If q divides x + y , we show that q divides n where, n = (x^q+y^q )/(x+y), we have y = -x (mod q) and , n = x^(q-1)-x^(q-2)*y + ... +y^(q-1) so, n = x^(q-1)-x^(q-2)*(-x)+...+(-x)^(q-1)=q*x^(q-1) (mod q), hence q divides n.

We also know q divides m , so q divides gcd(m, n), but by using lemma, gcd(m, n)=|(x^gcd(p, q)+y^gcd(p, q))/(x+y)|hence q divides |(x^gcd(p, q)+y^gcd(p, q))/(x+y)|, so gcd(p, q)>1 and since p & q are primes gcd(p, q)=p=q , so p divides x + y (because in this case q divides x + y) which is a contradiction with gcd (p, x + y)=1, and the proof is complete.

Ken wrote:

This is a direct consequence of a theorem proved by Legendre in 1798.

Every prime divisor of a^m + 1 is either of the form 2mx + 1 or divides a^w +1 where w is the quotient of n by an odd factor. [1] 

Thus if q is a prime which divides a^p + 1 for some integers a and p where p is prime, q must have the form 2mp + 1 for some integer m or q divides a +1. 

Consider  a^p + 1 = (a + 1)( a^(p - 1) - a^(p - 2) + a^(p - 3) - a^(p - 4) + . . .  + a^2 - a +1) = = 0 (mod q) for some integers a, p and q where (a, p) =1  and (a, q) = 1. Now if a +1 = = 0 (mod q) then the other factor (a^(p - 1) - a^(p - 2) + a^(p - 3) - a^(p - 4) + . . .  + a^2 - a +1) = = ( (-1)^(p - 1) - (-1)^(p - 2) + (-1)^(p - 3) - (-1)a^(p - 4) + . . .  + (-1)^2 - (-1) +1) = = p (mod q) so that p = q. Then let F(a)  = (a^p +1)/(a+1). We need to show that F is not divisible by (a +1). To show this,  it suffices to show that -1 is not a root of the polynomial F(a). Suppose that F(a) =  (a + 1) Q(a)  +  r where Q(a) = (a^(p - 1) - a^(p - 2) + a^(p - 3) - a^(p - 4) + . . .  + a^2 - a +1) and r an integer.  By the Factor Remainder, F(a) is divisible by (a + 1) only if r = 0. But we have already shown that Q(-1) = p > 0. Thus F(a) is not divisible by (a + 1) and the quantity (a^p + 1) has only one factor of the form (a + 1).

Next suppose that q does not divide (a + 1). Then q divides a^p +1 and q also divides (a^p +1)(a^p - 1) = a(2p) - 1. Let e be th smallest positive integer such that a^e = = 1 (mod q). Then by Euler’s Theorem, e divides q - 1.But e also divides 2p. Hence e divides (2p, q-1).  Since p is prime, (2p, q - 1) = 2 or 2p so that e = 2 or e = 2p. If e = 2p then there is an integer k such that 2pk = q -1 and q = 2kp +1. And all prime factors q of x^p + y^p have the form q = 2pk + 1. If e = 2, then  a^2 - 1 = = 0 (mod q) and a^2 - 1 = (a + 1)(a - 1) = = 0 (mod q). a = 1 implies that a^p +1 = 2 so that F(a) = 1 and hence q =1 which is not prime. Thus since q does not divide (a + 1), this case cannot occur.

Thus since F(a) = (a^p +1)/(a +1) is not divisible by (a + 1) all prime factors of F(a) have the form q = 2pk +1 where p and q are primes and k is an integer.

To transform the stated problem into the form used in this proof, it suffices to note that if (x, q) = (y, q) = 1 for some integers x, y and q where q is prime, then there is an integer s such that sy = = 1 (mod q). Then by multiplying (x^p + y^p) by s^p  and (x + y) by s respectively, we obtain {(xs)^p + (ys)^p}= = a^p + 1 and (xs + ys) = = a + 1 (mod q) respectively. 

1. L.E. Dickson, History of the Theory of Numbers, vol. I, Chelsea Publishing Company, New York, New York, (1952), p.382.

***