Maths Olympiad Prep

Library / /10 of 106

Number theory Difficulty 7.7 National olympiad, round 2 Find the answer

Find all the pairs of positive integers (x,p)(x,p) such that p is a prime, x2px \leq 2p and xp1x^{p-1} is a divisor of (p1)x+1 (p-1)^{x}+1.

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

Solution

To find all pairs of positive integers (x,p)(x, p), where pp is a prime, x2px \leq 2p, and xp1x^{p-1} divides (p1)x+1(p-1)^{x} + 1, we proceed as follows:

1. **Case 1: x=1x = 1.**

For x=1x = 1, we have (p1)x+1=(p1)+1=p(p-1)^{x} + 1 = (p-1) + 1 = p. Since 1p1=11^{p-1} = 1, 11 divides pp for any prime pp. Therefore, (x,p)=(1,p)(x, p) = (1, p) is a solution for any prime pp.

2. **Case 2: x=2x = 2.**

For x=2x = 2, we need to ensure 2p12^{p-1} divides (p1)2+1(p-1)^{2} + 1. We compute:
(p1)2+1=(p1)2+1=p22p+1+1=p22p+2. (p-1)^{2} + 1 = (p-1)^2 + 1 = p^2 - 2p + 1 + 1 = p^2 - 2p + 2.
Hence, we need 2p12^{p-1} to divide p22p+2p^2 - 2p + 2.

For p=2p = 2, we have x2×2=4x \leq 2 \times 2 = 4. Evaluating:
221=2 2^{2-1} = 2
and
(21)2+1=12+1=2. (2-1)^2 + 1 = 1^2 + 1 = 2.
Thus, 22 divides 22. Therefore, (x,p)=(2,2)(x, p) = (2, 2) is a valid solution.

3. **Case 3: x=3x = 3.**

For x=3x = 3, we need 3p13^{p-1} to divide (p1)3+1(p-1)^{3} + 1. For p=3p = 3, we have x2×3=6x \leq 2 \times 3 = 6. Evaluating:
331=9 3^{3-1} = 9
and
(31)3+1=23+1=8+1=9. (3-1)^3 + 1 = 2^3 + 1 = 8 + 1 = 9.
Here, 99 divides 99. Therefore, (x,p)=(3,3)(x, p) = (3, 3) is another solution.

After checking these cases, we conclude that the set of solution pairs (x,p)(x, p) includes:
(2,2),(3,3),(1,p) for any prime p. \boxed{(2, 2), (3, 3), (1, p) \text{ for any prime } p}.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.