Maths Olympiad Prep

Library / /33 of 121

Number theory Difficulty 5.6 AIME, harder Prove it India

Problem:

Let p1<p2<p3<p4p_{1} < p_{2} < p_{3} < p_{4} and q1<q2<q3<q4q_{1} < q_{2} < q_{3} < q_{4} be two sets of prime numbers such that p4p1=8p_{4} - p_{1} = 8 and q4q1=8q_{4} - q_{1} = 8. Suppose p1>5p_{1} > 5 and q1>5q_{1} > 5. Prove that 3030 divides p1q1p_{1} - q_{1}.

Solution

Solution:

Since p4p1=8p_{4} - p_{1} = 8, and no prime is even, we observe that {p1,p2,p3,p4}\{p_{1}, p_{2}, p_{3}, p_{4}\} is a subset of {p1,p1+2,p1+4,p1+6,p1+8}\{p_{1}, p_{1} + 2, p_{1} + 4, p_{1} + 6, p_{1} + 8\}. Moreover p1p_{1} is larger than 33. If p11(mod3)p_{1} \equiv 1 \pmod{3}, then p1+2p_{1} + 2 and p1+8p_{1} + 8 are divisible by 33. Hence we do not get 44 primes in the set {p1,p1+2,p1+4,p1+6,p1+8}\{p_{1}, p_{1} + 2, p_{1} + 4, p_{1} + 6, p_{1} + 8\}. Thus p12(mod3)p_{1} \equiv 2 \pmod{3} and p1+4p_{1} + 4 is not a prime. We get p2=p1+2p_{2} = p_{1} + 2, p3=p1+6p_{3} = p_{1} + 6, p4=p1+8p_{4} = p_{1} + 8.

Consider the remainders of p1,p1+2,p1+6,p1+8p_{1}, p_{1} + 2, p_{1} + 6, p_{1} + 8 when divided by 55. If p12(mod5)p_{1} \equiv 2 \pmod{5}, then p1+8p_{1} + 8 is divisible by 55 and hence is not a prime. If p13(mod5)p_{1} \equiv 3 \pmod{5}, then p1+2p_{1} + 2 is divisible by 55. If p14(mod5)p_{1} \equiv 4 \pmod{5}, then p1+6p_{1} + 6 is divisible by 55. Hence the only possibility is p11(mod5)p_{1} \equiv 1 \pmod{5}.

Thus we see that p11(mod2)p_{1} \equiv 1 \pmod{2}, p12(mod3)p_{1} \equiv 2 \pmod{3} and p11(mod5)p_{1} \equiv 1 \pmod{5}. We conclude that p111(mod30)p_{1} \equiv 11 \pmod{30}.

Similarly q111(mod30)q_{1} \equiv 11 \pmod{30}. It follows that 3030 divides p1q1p_{1} - q_{1}.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.