Maths Olympiad Prep

Library / /7 of 41

Number theory Difficulty 4.7 AIME Prove it New Zealand

Problem:
Determine all prime numbers pp such that p26p^{2} - 6 and p2+6p^{2} + 6 are both prime numbers.

Solutions — 2

Solution 1

Solution:
If p>5p > 5 then the units digit of pp must be 1, 3, 7 or 9.
- If the units digit of pp is 1 or 9 then the units digit of p2p^{2} is 1. Therefore the units digit of p26p^{2} - 6 is 5. Since p26>5p^{2} - 6 > 5 this means that p26p^{2} - 6 is not prime.
- If the units digit of pp is 3 or 7 then the units digit of p2p^{2} is 9. Therefore the units digit of p2+6p^{2} + 6 is 5. Since p2+6>5p^{2} + 6 > 5 this means that p2+6p^{2} + 6 is not prime.
Therefore we must have p5p \leq 5 . Hence pp must be 2, 3 or 5.
- If p=2p = 2 then p2+6=10p^{2} + 6 = 10 is not prime.
- If p=3p = 3 then p2+6=15p^{2} + 6 = 15 is not prime.
- If p=5p = 5 then p2±6p^{2} \pm 6 are 19 and 31 which are both prime.
Therefore the only answer is p=5p = 5 .

Solution 2

Solution:
Consider the following product modulo 5.
p(p26)(p2+6)=p536pp5p(mod5)p(p^{2} - 6)(p^{2} + 6) = p^{5} - 36p \equiv p^{5} - p \pmod {5}
By Fermat's Little Theorem, this product is 0 (mod 5). So if pp , p26p^{2} - 6 and p2+6p^{2} + 6 are all prime numbers then at least one of them must be equal to 5.
- If p=5p = 5 then 6p21=296p^{2} - 1 = 29 and 6p2+1=316p^{2} + 1 = 31 . This is one solution.
- If 6p21=56p^{2} - 1 = 5 then p=±1p = \pm 1 . Neither 1 nor 1-1 is prime, so this case leads to no solutions.
- If 6p2+1=56p^{2} + 1 = 5 then pp is not an integer. No solutions in this case.
Therefore the only solution is p=5p = 5 .

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.