Maths Olympiad Prep

Track / Stage 5 / 243 of 400 #843 of 1964

Problem 843

AIME late
Number theory Difficulty 5.6 Find the answer

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

untranslated text remains unchanged.

A number or a short expression. Spacing, $ signs and \frac vs / are all fine.

Official solution

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

By Fermat's Little Theorem, q5q5q \mid 5^{q}-5, thus q30q \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 5pq5 \mid p q, without loss of generality, let p=5p=5, then 5q55+5q5 q \mid 5^{5}+5^{q}, so q5q1+625q \mid 5^{q-1}+625.

When q=5q=5, the prime pair (5,5)(5,5) meets the requirements. When q5q \neq 5, by Fermat's Little Theorem, we have q5q11q \mid 5^{q-1}-1, hence q626q \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 pq5p1+5q1p q \mid 5^{p-1}+5^{q-1}, so
5p1+5q10(modp). 5^{p-1}+5^{q-1} \equiv 0(\bmod p).

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

Let p1=2k(2r1),q1=2l(2s1)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 klk \leqslant l, then from (2), (3) it is easy to see
1=12lk(2s1)(5p1)2lk(2s1)=5l2(2Γ1)(2s1)= 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)}=
(5q1)2r1(1)2r11(modp)\left(5^{q-1}\right)^{2 r-1} \equiv(-1)^{2 r-1} \equiv-1(\bmod p),
which contradicts p2p \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 and solution reproduced as published; topic, difficulty and ordering added by this site.