Maths Olympiad Prep

Library / /20 of 38

Number theory Difficulty 6.8 National olympiad Prove it China

Find all triples (p,q,n)(p, q, n) such that
qn+23n+2(modpn),pn+23n+2(modqn) q^{n+2} \equiv 3^{n+2} \pmod{p^n}, \quad p^{n+2} \equiv 3^{n+2} \pmod{q^n}
where pp, qq are positive odd primes and n>1n > 1 is an integer.

Solution

It is easy to check that (3,3,n)(3, 3, n) (n=2,3,n = 2, 3, \dots) satisfy both equations. Now let (p,q,n)(p, q, n) be another triple satisfying the condition. Then we must have pqp \ne q, p3p \ne 3, q3q \ne 3. We may assume that q>p5q > p \ge 5.

If n=2n = 2, then q2p434q^2 \mid p^4 - 3^4, or q2(p232)(p2+32)q^2 \mid (p^2 - 3^2)(p^2 + 3^2). Then either q2p232q^2 \mid p^2 - 3^2 or q2p2+32q^2 \mid p^2 + 3^2, since qq cannot divide both p232p^2 - 3^2 and p2+32p^2 + 3^2. On the other hand, 0<p232<q20 < p^2 - 3^2 < q^2, 12(p2+32)<p2<q2\frac{1}{2}(p^2 + 3^2) < p^2 < q^2. This leads to a contradiction.

So n3n \ge 3. From pnqn+23n+2p^n \mid q^{n+2} - 3^{n+2}, qnpn+23n+2q^n \mid p^{n+2} - 3^{n+2}, we get
pnpn+2+qn+23n+2,qnpn+2+qn+23n+2. p^n \mid p^{n+2} + q^{n+2} - 3^{n+2}, \quad q^n \mid p^{n+2} + q^{n+2} - 3^{n+2}.
Since p<qp < q, and pp, qq primes, we have
pnqnpn+2+qn+23n+2.1 p^n q^n \mid p^{n+2} + q^{n+2} - 3^{n+2}. \qquad \textcircled{1}
Then pnqnpn+2+qn+23n+2<2qn+2p^n q^n \le p^{n+2} + q^{n+2} - 3^{n+2} < 2q^{n+2}. That means pn<2q2p^n < 2q^2.

As qnpn+23n+2q^n \mid p^{n+2} - 3^{n+2} and p>3p > 3, we have qnpn+23n+2<pn+2q^n \le p^{n+2} - 3^{n+2} < p^{n+2}, and consequently q<p1+2nq < p^{1+\frac{2}{n}}. Since pn<2q2p^n < 2q^2, we have pn<2p2+4n<p3+4np^n < 2p^{2+\frac{4}{n}} < p^{3+\frac{4}{n}}. So n<3+4nn < 3+\frac{4}{n}, and we get n=3n = 3. Then p3q535p^3 \mid q^5 - 3^5, q3p535q^3 \mid p^5 - 3^5.

From 5535=2×11×1315^5 - 3^5 = 2 \times 11 \times 131, we know p>5p > 5; from p3q535p^3 \mid q^5 - 3^5 we know pq535p \mid q^5 - 3^5. By Fermat's little theorem, we get pqp13p1p \mid q^{p-1} - 3^{p-1}. Then pq(5,p1)3(5,p1)p \mid q^{(5, p-1)} - 3^{(5, p-1)}.

If (5,p1)=1(5, p-1) = 1, then pq3p \mid q-3. From
q535q3=q4+q33+q232+q33+345×34(modp) \begin{aligned} \frac{q^5 - 3^5}{q - 3} &= q^4 + q^3 \cdot 3 + q^2 \cdot 3^2 + q \cdot 3^3 + 3^4 \\ &\equiv 5 \times 3^4 \pmod{p} \end{aligned}
and p5p \ge 5, we get pq535q3p \nmid \frac{q^5 - 3^5}{q - 3}. So p3q3p^3 \mid q - 3. From q3p535q^3 \mid p^5 - 3^5, we get q3p535<p5=(p3)53<q53q^3 \le p^5 - 3^5 < p^5 = (p^3)^{\frac{5}{3}} < q^{\frac{5}{3}}. This is a contradiction.

So we have (5,p1)1(5, p-1) \ne 1, and that means 5p15 \mid p-1. In a similar way, we have 5q15 \mid q-1. As (q,p3)=1(q, p-3) = 1 (since q>p7q > p \ge 7) and q3p535q^3 \mid p^5 - 3^5, we know that q3p535p3q^3 \mid \frac{p^5 - 3^5}{p-3}. Then
q3p535p3=p4+p33+p232+p33+34. q^3 \le \frac{p^5 - 3^5}{p - 3} = p^4 + p^3 \cdot 3 + p^2 \cdot 3^2 + p \cdot 3^3 + 3^4.
From 5p15 \mid p-1 and 5q15 \mid q-1, we get p11p \ge 11 and q31q \ge 31. So
q3p4(1+3p+(3p)2+(3p)3+(3p)4) q^3 \le p^4 \left( 1 + \frac{3}{p} + \left(\frac{3}{p}\right)^2 + \left(\frac{3}{p}\right)^3 + \left(\frac{3}{p}\right)^4 \right)
<p4113p118p4. < p^4 \cdot \frac{1}{1 - \frac{3}{p}} \le \frac{11}{8} p^4.
Then we have p>(811)14q34p > \left(\frac{8}{11}\right)^{\frac{1}{4}} q^{\frac{3}{4}}. Consequently,
p5+q535p3q3<p2q3+q2p3<1q+(118)3413114<1. \frac{p^5 + q^5 - 3^5}{p^3 q^3} < \frac{p^2}{q^3} + \frac{q^2}{p^3} < \frac{1}{q} + \left(\frac{11}{8}\right)^{\frac{3}{4}} \frac{1}{31^{\frac{1}{4}}} < 1.
But this contradicts ① which says p3q3p5+q535p^3 q^3 \mid p^5 + q^5 - 3^5.

So we reach the conclusion that (3,3,n)(3, 3, n) (n=2,3,n = 2, 3, \dots) are all the triples that satisfy the conditions.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.