Maths Olympiad Prep

Track / Stage 5 / 290 of 400 #890 of 1964

Problem 890

AIME late
Number theory Difficulty 5.6 Find the answer

Three, (50 points) Find all prime pairs (p,q)(p, q) such that pq∣5p+5qp q \mid 5^{p}+5^{q}.

untranslated text remains unchanged.

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

Next problem →

Official solution

Three, Solution: If 2∣pq2 \mid p q, without loss of generality, let p=2p=2, then 2q∣52+5q2 q \mid 5^{2}+5^{q}, so q∣5q+25q \mid 5^{q}+25.

By Fermat's Little Theorem, q∣5q−5q \mid 5^{q}-5, thus q∣30q \mid 30, i.e., q=2q=2, 3, 5. It is easy to verify that the prime pair (2,2)(2,2) does not meet the requirements, while (2,3)(2,3) and (2,5)(2,5) do meet the requirements.

If pqp q is odd and 5∣pq5 \mid p q, without loss of generality, let p=5p=5, then 5q∣55+5q5 q \mid 5^{5}+5^{q}, so q∣5q−1+625q \mid 5^{q-1}+625.

When q=5q=5, the prime pair (5,5)(5,5) meets the requirements. When q≠5q \neq 5, by Fermat's Little Theorem, we have q∣5q−1−1q \mid 5^{q-1}-1, hence q∣626q \mid 626. Since qq is an odd prime, and the only odd prime factor of 626 is 313, so q=313q=313. After verification, the prime pair (5,313)(5,313) meets the requirements.

If p,qp, q are neither 2 nor 5, then pq∣5p−1+5q−1p q \mid 5^{p-1}+5^{q-1}, so
5p−1+5q−1≡0( mod p). 5^{p-1}+5^{q-1} \equiv 0(\bmod p).

By Fermat's Little Theorem, we get 5p−1≡1( mod p)5^{p-1} \equiv 1(\bmod p),
so from (1) and (2) we have
5q−1≡−1( mod p). 5^{q-1} \equiv-1(\bmod p).

Let p−1=2k(2r−1),q−1=2l(2s−1)p-1=2^{k}(2 r-1), q-1=2^{l}(2 s-1), where kk, l,r,sl, r, s are positive integers.
If k⩽lk \leqslant l, then from (2), (3) it is easy to see
1=12l−k(2s−1)≡(5p−1)2l−k(2s−1)=5l2(2Γ−1)(2s−1)= 1=1^{2^{l-k}(2 s-1)} \equiv\left(5^{p-1}\right)^{2^{l-k}(2 s-1)}=5_{l}^{2(2 \Gamma-1)(2 s-1)}=
(5q−1)2r−1≡(−1)2r−1≡−1( mod p)\left(5^{q-1}\right)^{2 r-1} \equiv(-1)^{2 r-1} \equiv-1(\bmod p),
which contradicts p≠2p \neq 2! So k>lk>l.
Similarly, we have k<lk<l, which is a contradiction! Therefore, there are no (p,q)(p, q) that meet the requirements in this case.

In summary, all prime pairs (p,q)(p, q) that meet the requirements are
(2,3),(3,2),(2,5),(5,2),(5,5),(5,313) and  (2,3),(3,2),(2,5),(5,2),(5,5),(5,313) \text { and }

Source: NuminaMath-1.5, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.