Maths Olympiad Prep

Library / /2 of 73

Number theory Difficulty 7.3 National Olympiad, round 2 Prove it Turkey

Find all pairs (p,q)(p, q) of prime numbers satisfying
2p=2q2+q! 2^p = 2^{q-2} + q!

Solution

Answer: (p,q)=(3,3),(7,5)(p, q) = (3, 3), (7, 5).

If q=2q = 2 then no pair (p,2)(p, 2) satisfies the equation. If q=3q = 3 and q=5q = 5 then the only pairs satisfying the equation are (3,3)(3, 3) and (5,7)(5, 7), respectively.

Let us show that there is no solution for q7q \ge 7. Consider the binary representation of qq: q=2a1+2a2++2arq = 2^{a_1} + 2^{a_2} + \cdots + 2^{a_r} where 0a1<a2<<ar0 \le a_1 < a_2 < \cdots < a_r are integers and rr is the number of 1's in the binary representation of qq. For all 1kr1 \le k \le r and 1iak1 \le i \le a_k the number 2ak2i\frac{2^{a_k}}{2^i} is an integer. Furthermore, when i>aki > a_k, we get 2ak2i=0\left\lfloor \frac{2^{a_k}}{2^i} \right\rfloor = 0.

Finally, we have i=12ak2i=2ak1\sum_{i=1}^{\infty} \left\lfloor \frac{2^{a_k}}{2^i} \right\rfloor = 2^{a_k} - 1. Therefore, v2(q!)v_2(q!), the highest power of 22 in q!q! can be written as
v2(q!)=i=1q2i=qr. v_2(q!) = \sum_{i=1}^{\infty} \left\lfloor \frac{q}{2^i} \right\rfloor = q - r.
The original equation is equivalent to 2q2(2pq+21)=q!2^{q-2}(2^{p-q+2}-1) = q!, where pq+2>0p-q+2 > 0. Hence v2(q!)=q2v_2(q!) = q-2. Therefore, r=2r=2 and q=2a1+2a2q = 2^{a_1}+2^{a_2}. Since qq is a prime number, we get a1=0a_1 = 0 and a2=2ta_2 = 2^t for some non-negative integer tt (qq is a Fermat prime).

As q7q \ge 7 we have 2pq+21(mod7)2^{p-q+2} \equiv 1 \pmod 7 and pq+20(mod3)p-q+2 \equiv 0 \pmod 3. Using the fact q=22t+12(mod3)q = 2^{2t} + 1 \equiv 2 \pmod 3 we get 3p3 \mid p and hence p=3p=3. For q7q \ge 7 no pair (3,q)(3, q) satisfies the equation. Done.

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.