Maths Olympiad Prep

Library / /1 of 68

Number theory Difficulty 4.3 AIME Prove it Estonia

Find all prime numbers pp such that p12\frac{p-1}{2} and p+14\frac{p+1}{4} are prime numbers, too.

Solutions — 2

Solution 1

Let q=p12q = \frac{p-1}{2} and r=p+14r = \frac{p+1}{4}; then p=4r1p = 4r-1 and q=4r22=2r1q = \frac{4r-2}{2} = 2r-1. Consider all remainders that can be left when rr is divided by 33:
* If r1(mod3)r \equiv 1 \pmod{3} then 4r10(mod3)4r-1 \equiv 0 \pmod{3}, i.e., 4r14r-1 is divisible by 33. Thus p=3p=3. But then r=1r=1 which is not a prime.
* If r2(mod3)r \equiv 2 \pmod{3} then 2r10(mod3)2r-1 \equiv 0 \pmod{3}, i.e., 2r12r-1 is divisible by 33. Thus q=3q=3, whence r=2r=2 and p=7p=7. All three are primes indeed.
* If r0(mod3)r \equiv 0 \pmod{3}, i.e., rr is divisible by 33, then r=3r=3. Thus q=5q=5 and p=11p=11 which are primes, too.
Consequently, pp can be either 77 or 1111.

Solution 2

Out of three consecutive integers p1p-1, pp, p+1p+1 one is divisible by 33. Division by 22 or 44 does not change divisibility by 33 since 22 and 44 are coprime with 33. Thus also out of integers pp, p12\frac{p-1}{2}, p+14\frac{p+1}{4} one is divisible by 33. If these integers are prime, the one divisible by 33 must be 33. Consider all possible cases:
* If p=3p = 3 then p12=1\frac{p-1}{2} = 1 but 11 is not prime.
* If p12=3\frac{p-1}{2} = 3 then p=7p = 7 and p+14=2\frac{p+1}{4} = 2. All three are primes indeed.
* If p+14=3\frac{p+1}{4} = 3 then p=11p = 11 and p12=5\frac{p-1}{2} = 5. All three are primes indeed.
Consequently, pp can be either 77 or 1111.

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.