Problems & Puzzles:
Puzzles
Puzzle 276.
Prime factors of (x^n+y^n)/(x+y)
J. Bellingham sent the
following puzzle:
For
integers x, y, (x+y), n which have no common factors and n being prime, it
is easy to prove (x^n + y^n) / (x + y) is 1 mod n.
Can you find an
example where the prime factors of (x^n + y^n) / (x + y) are not ALL 1 mod
n or prove that they all will be 1 mod n.
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)^(q1)1 (I.2) so from (I.1) & (I.2) we have , q
divides gcd((t*y)^(2p)1, (t*y)^(q1)1) hence by using lemma , q
divides (t*y)^gcd(2p, q1)1, since 2p & q1 are even numbers and p is
prime ,gcd (2p, q1) = 2 or 2 p, If we show that the first case doesn't
happen, then gcd (2p, q1) = 2p so q is of the form 2*k*p + 1. gcd (2p,
q1) != 2 , because if gcd(2p, q1) = 2 since q divides (t*y)^gcd(2p,
q1)1 then, q divides (t*y)^21 (I.3) we also know q divides (t*x)1 so
, q divides ( t*x)^21 (I.4) and from (I.3) & (I.4) we have , q divides
t^2(x^2y^2) , but q doesn't divide t so q divides x^2y^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^(q1)x^(q2)*y + ... +y^(q1) so, n =
x^(q1)x^(q2)*(x)+...+(x)^(q1)=q*x^(q1) (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,
q1). 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.
***
