Maths Olympiad Prep

Library / /207 of 520

Number theory Difficulty 6.3 National olympiad Find the answer

Find all prime numbers pp for which there exist positive integers x,yx, y and zz such that the number

xp+yp+zpxyz x^{p}+y^{p}+z^{p}-x-y-z

is a product of exactly three distinct prime numbers.

A number or a short expression. Spacing and $ signs are ignored.

Solutions — 2

Solution 1

Let A=xp+yp+zpxyz A = x^p + y^p + z^p - x - y - z . For p=2 p = 2 , we take x=y=4 x = y = 4 and z=3 z = 3 . Then A=30=235 A = 30 = 2 \cdot 3 \cdot 5 . For p=3 p = 3 we can take x=3 x = 3 and y=2 y = 2 and z=1 z = 1 . Then again A=30=235 A = 30 = 2 \cdot 3 \cdot 5 . For p=5 p = 5 we can take x=2 x = 2 and y=1 y = 1 and z=1 z = 1 . Again A=30=235 A = 30 = 2 \cdot 3 \cdot 5 .

Assume now that p7 p \geq 7 . Working modulo 2 and modulo 3 we see that A A is divisible by both 2 and 3. Moreover, by Fermat's Little Theorem, we have

xp+yp+zpxyzx+y+zxyz=0modp. x^p + y^p + z^p - x - y - z \equiv x + y + z - x - y - z = 0 \bmod p.

Therefore, by the given condition, we have to solve the equation

xp+yp+zpxyz=6p. x^p + y^p + z^p - x - y - z = 6p.

If one of the numbers x,y x, y and z z is bigger than or equal to 2, let's say x2 x \geq 2 , then

6pxpx=x(xp11)2(2p11)=2p2. 6p \geq x^p - x = x(x^{p-1} - 1) \geq 2(2^{p-1} - 1) = 2^p - 2.

It is easy to check by induction that 2n2>6n 2^n - 2 > 6n for all natural numbers n6 n \geq 6 . This contradiction shows that there are no more values of p p which satisfy the required property.

Remark. There are a couple of other ways to prove that 2p2>6p 2^p - 2 > 6p for p7 p \geq 7 . For example, we can use the Binomial Theorem as follows:

2p21+p+p(p1)2+p(p1)(p2)621+p+3p+5p2>6p. 2^p - 2 \geq 1 + p + \frac{p(p-1)}{2} + \frac{p(p-1)(p-2)}{6} - 2 \geq 1 + p + 3p + 5p - 2 > 6p.

We can also use Bernoulli's Inequality as follows:

2p2=8(1+1)p328(1+(p3))2=8p18>6p. 2^p - 2 = 8(1+1)^{p-3} - 2 \geq 8(1 + (p-3)) - 2 = 8p - 18 > 6p.

The last inequality is true for p11 p \geq 11 . For p=7 p = 7 we can see directly that 2p2>6p 2^p - 2 > 6p .

One can also use calculus to show that f(x)=2x6x f(x) = 2^x - 6x is increasing for x5 x \geq 5 .

Solution 2

To find all prime numbers p p for which there exist positive integers x x , y y , and z z such that the number xp+yp+zpxyz x^p + y^p + z^p - x - y - z is a product of exactly three distinct prime numbers, we proceed as follows:

1. **Verification for p=2,3,5 p = 2, 3, 5 **:
- For p=2 p = 2 :
x2+y2+z2xyz x^2 + y^2 + z^2 - x - y - z
Choose (x,y,z)=(1,1,6) (x, y, z) = (1, 1, 6) :
12+12+62116=1+1+36116=30 1^2 + 1^2 + 6^2 - 1 - 1 - 6 = 1 + 1 + 36 - 1 - 1 - 6 = 30
30=2×3×5 30 = 2 \times 3 \times 5 , which is a product of three distinct primes.

- For p=3 p = 3 :
x3+y3+z3xyz x^3 + y^3 + z^3 - x - y - z
Choose (x,y,z)=(1,2,3) (x, y, z) = (1, 2, 3) :
13+23+33123=1+8+27123=30 1^3 + 2^3 + 3^3 - 1 - 2 - 3 = 1 + 8 + 27 - 1 - 2 - 3 = 30
30=2×3×5 30 = 2 \times 3 \times 5 , which is a product of three distinct primes.

- For p=5 p = 5 :
x5+y5+z5xyz x^5 + y^5 + z^5 - x - y - z
Choose (x,y,z)=(1,1,2) (x, y, z) = (1, 1, 2) :
15+15+25112=1+1+32112=30 1^5 + 1^5 + 2^5 - 1 - 1 - 2 = 1 + 1 + 32 - 1 - 1 - 2 = 30
30=2×3×5 30 = 2 \times 3 \times 5 , which is a product of three distinct primes.

2. **Proof of necessity for p>5 p > 5 **:
- Suppose p>5 p > 5 . Note that by Fermat's Little Theorem, for any integer a a :
apa(modp) a^p \equiv a \pmod{p}
Therefore:
xpx(modp),ypy(modp),zpz(modp) x^p \equiv x \pmod{p}, \quad y^p \equiv y \pmod{p}, \quad z^p \equiv z \pmod{p}
This implies:
xp+yp+zpxyz0(modp) x^p + y^p + z^p - x - y - z \equiv 0 \pmod{p}
Hence, p(xp+yp+zpxyz) p \mid (x^p + y^p + z^p - x - y - z) .

- Additionally, for any odd prime p p and positive integer a a :
apa(mod2)andapa(mod3) a^p \equiv a \pmod{2} \quad \text{and} \quad a^p \equiv a \pmod{3}
Proof:
- If 2a 2 \mid a , then ap a^p and a a are both even.
- If 2a 2 \nmid a , then ap a^p and a a are both odd.
- If 3a 3 \mid a , then 3ap 3 \mid a^p .
- If 3a 3 \nmid a , then by Fermat's Little Theorem, ap11(mod3) a^{p-1} \equiv 1 \pmod{3} , so apa(mod3) a^p \equiv a \pmod{3} .

- Thus:
6(xp+yp+zpxyz) 6 \mid (x^p + y^p + z^p - x - y - z)
This implies:
xp+yp+zpxyz=6kfor some integer k x^p + y^p + z^p - x - y - z = 6k \quad \text{for some integer } k
Since xp+yp+zpxyz x^p + y^p + z^p - x - y - z is a product of exactly three distinct primes, let xp+yp+zpxyz=p1p2p3 x^p + y^p + z^p - x - y - z = p_1 p_2 p_3 where p1,p2,p3 p_1, p_2, p_3 are distinct primes.

- For p>7 p > 7 , consider:
xp+yp+zpxyz=(xpx)+(ypy)+(zpz) x^p + y^p + z^p - x - y - z = (x^p - x) + (y^p - y) + (z^p - z)
Since at least one of x,y,z x, y, z is greater than 1, we have:
(xpx)+(ypy)+(zpz)2p2 (x^p - x) + (y^p - y) + (z^p - z) \ge 2^p - 2
For p>7 p > 7 :
2p2>6p 2^p - 2 > 6p
This leads to a contradiction because xp+yp+zpxyz x^p + y^p + z^p - x - y - z cannot be a product of exactly three distinct primes if it exceeds 6p 6p .

Therefore, the only possible primes p p are 2,3, 2, 3, and 5 5 .

The final answer is 2,3,5 \boxed{2, 3, 5} .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.