Maths Olympiad Prep

Library / /48 of 86

Number theory Difficulty 6.0 AIME, harder Prove it Estonia

We call a prime number pp cute if there exists a prime qq so that both pq2pq - 2 and pq+2pq + 2 are also primes. We call pp wonderful if both pp and p+2p+2 are cute primes. Find all wonderful numbers.

Solution

Let pp be a cute prime. The numbers pq2pq - 2, pqpq and pq+2pq + 2 give all the possible remainders modulo 33, so one of them must be divisible by 33. If 3pq23 \mid pq - 2, then pq2=3pq - 2 = 3 and pq=5pq = 5, which is impossible, as pp, qq are primes. Similarly if 3pq+23 \mid pq + 2, then pq+2=3pq + 2 = 3 and pq=1pq = 1, which is also impossible. So 3pq3 \mid pq, which means that either p=3p = 3 or q=3q = 3. Given that in the case p=3p = 3 we can have q=3q = 3, we have shown that pp is cute iff both 3p23p - 2 and 3p+23p + 2 are primes.

Therefore pp is wonderful if pp, p+2p + 2, 3p23p - 2, 3p+23p + 2, 3p+43p + 4 and 3p+83p + 8 are all primes. We know that the numbers 3p23p - 2, 3p3p, 3p+23p + 2, 3p+43p + 4 and 3p+63p + 6 give all of the possible remainders modulo 55, so one of those numbers is divisible by 55. If it's 3p23p - 2, 3p+23p + 2 or 3p+43p + 4, then due to primality it must be equal to 55, but then pp is not prime. If it's 3p3p or 3p+63p + 6, then either 5p5 \mid p or 5p+25 \mid p + 2 respectively. Thus p=3p = 3 or p=5p = 5. We can verify that both work.

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.