Maths Olympiad Prep

Library / /3 of 6

Number theory Difficulty 5.4 AIME, harder Prove it Thailand

Let mm and nn be positive integers. Prove that if m4n+11m^{4n+1} - 1 is a prime number then there exists an integer t0t \ge 0 such that n=2tn = 2^t.

Solution

Let pp be an odd prime where pnp \mid n. Then,
4n+1=(4np)p+1=(4np+1)((4np)p1(4np)p2+4np+1)=(4np+1)x \begin{aligned} 4^n + 1 &= (4^{\frac{n}{p}})^p + 1 = (4^{\frac{n}{p}} + 1)((4^{\frac{n}{p}})^{p-1} - (4^{\frac{n}{p}})^{p-2} + \dots - 4^{\frac{n}{p}} + 1) \\ &= (4^{\frac{n}{p}} + 1)x \end{aligned}

where x=(4np)p1(4np)p2+4np+1>1x = (4^{\frac{n}{p}})^{p-1} - (4^{\frac{n}{p}})^{p-2} + \dots - 4^{\frac{n}{p}} + 1 > 1. So, we have
m4n+11=m(4np+1)x1=(m4np+11)(m(4np+1)(x1)+m(4np+1)(x2)++m4np+1+1). \begin{aligned} m^{4n+1} - 1 &= m^{(4^{\frac{n}{p}}+1)x} - 1 \\ &= (m^{4^{\frac{n}{p}}+1} - 1)(m^{(4^{\frac{n}{p}}+1)(x-1)} + m^{(4^{\frac{n}{p}}+1)(x-2)} + \dots + m^{4^{\frac{n}{p}}+1} + 1). \end{aligned}
Since m4n+11m^{4n+1} - 1 is a prime and x>1x > 1, m4np+11=1m^{4^{\frac{n}{p}}+1} - 1 = 1. Thus, m4np+1=2m^{4^{\frac{n}{p}}+1} = 2, and so m=2m = 2 and 4np+1=14^{\frac{n}{p}}+1 = 1. Therefore, np+1=0\frac{n}{p} + 1 = 0, which is a contradiction. We conclude that nn has no odd prime factors, hence is a power of 2.

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.