Maths Olympiad Prep

Library / /5 of 37

Number theory Difficulty 6.2 National olympiad Find the answer

Find all the pairs of prime numbers (p,q) (p,q) such that pq|5 p 5 q.\text{pq|5 p 5 q.}

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

To find all pairs of prime numbers (p,q)(p, q) such that pq5p+5qpq \mid 5^p + 5^q, we consider several cases:

1. **Case 1: Either pp or qq is 2.**
- Assume p=2p = 2. Then 2q52+5q2q \mid 5^2 + 5^q.
- This simplifies to 2q25+5q2q \mid 25 + 5^q.
- Since 251(mod2)25 \equiv 1 \pmod{2}, we have 5q+10(modq)5^q + 1 \equiv 0 \pmod{q}, implying q30q \mid 30.
- The prime divisors of 30 are 2, 3, and 5. Since q2q \neq 2, the possible values for qq are 3 and 5.
- Thus, the pairs (p,q)(p, q) are (2,3)(2, 3) and (2,5)(2, 5).

2. **Case 2: p=q=5p = q = 5.**
- Clearly, 5255+555^2 \mid 5^5 + 5^5, so (5,5)(5, 5) is a solution.

3. **Case 3: p=5p = 5 and q5q \neq 5.**
- Then 5q55+5q5q \mid 5^5 + 5^q.
- This simplifies to 5q3125+5q5q \mid 3125 + 5^q.
- Since 31250(mod5)3125 \equiv 0 \pmod{5}, we have 5q+31250(modq)5^q + 3125 \equiv 0 \pmod{q}, implying q3126q \mid 3126.
- The prime divisors of 3126 are 2 and 313. Thus, the pairs (p,q)(p, q) are (5,2)(5, 2) and (5,313)(5, 313).

4. **Case 4: p5p \neq 5 and q5q \neq 5.**
- Assume p>qp > q. Then pq5p+5qpq \mid 5^p + 5^q.
- This implies 5q(5pq+1)0(modpq)5^q(5^{p-q} + 1) \equiv 0 \pmod{pq}.
- Therefore, 5pq1(modq)5^{p-q} \equiv -1 \pmod{q} and ordq(5)2(pq)\text{ord}_q(5) \mid 2(p-q).
- Since ordq(5)pq\text{ord}_q(5) \nmid p-q, we get a contradiction in the valuation of 2, leading to no further solutions.

Combining all cases, the pairs of prime numbers (p,q)(p, q) that satisfy the condition are:
(2,3),(2,5),(3,2),(5,2),(5,5),(5,313),(313,5) \boxed{(2, 3), (2, 5), (3, 2), (5, 2), (5, 5), (5, 313), (313, 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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.