Maths Olympiad Prep

Library / /174 of 520

Number theory Difficulty 5.9 AIME, harder Prove it

6. Let mNm \in \mathbf{N}^{*}. Prove: If
(2m+1+1)(32m+1),\left(2^{m+1}+1\right) \mid\left(3^{2^{m}}+1\right),

then 2m+1+12^{m+1}+1 is a prime number.

Solution

6. Let q=2m+1+1q=2^{m+1}+1, by the condition we know 32m1(modq)3^{2^{m}} \equiv-1(\bmod q), hence 32m+11(mod3^{2^{m+1}} \equiv 1(\bmod q)q). This indicates δq(3)2m+1\delta_{q}(3) \mid 2^{m+1}, but δq(3)×2m\delta_{q}(3) \times 2^{m}. Therefore, δq(3)=2m+1\delta_{q}(3)=2^{m+1}.

On the other hand, by Euler's theorem, we know 3φ(q)1(modq)3^{\varphi(q)} \equiv 1(\bmod q), so 2m+1φ(q)2^{m+1} \mid \varphi(q), i.e., (q1)φ(q)(q-1) \mid \varphi(q). Combining φ(q)q1\varphi(q) \leqslant q-1, we know φ(q)=q1\varphi(q)=q-1, thus qq is a prime.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.