Maths Olympiad Prep

Library / /295 of 520

Number theory Difficulty 6.2 National olympiad Prove it

14. Prove: There exist infinitely many nNn \in \mathbf{N}^{*}, such that n(2n+2)n \mid\left(2^{n}+2\right).

Solution

14. The smallest two nn that satisfy the condition are n=2,6n=2,6. Based on this analysis, we prove the following strengthened proposition: there exist infinitely many positive even numbers n1<n2<n_{1}<n_{2}<\cdots such that for any kNk \in \mathbf{N}^{*}, we have nk(2nk+2)n_{k} \mid\left(2^{n_{k}}+2\right), and (nk1)(2nk+1)\left(n_{k}-1\right) \mid\left(2^{n_{k}}+1\right).

We use mathematical induction to prove this proposition. Let n1=2n_{1}=2, and for any kNk \in \mathbf{N}^{*}, let nk+1=2nk+2n_{k+1}=2^{n_{k}}+2. We claim that the sequence defined in this way satisfies the proposition.

When k=1k=1, it is clearly true. Assume that nk(2nk+2)n_{k} \mid\left(2^{n_{k}}+2\right) and (nk1)(2nk+1)\left(n_{k}-1\right) \mid\left(2^{n_{k}}+1\right). Then nk+1=2nk+2n_{k+1}=2^{n_{k}}+2 is even, and 2nk+2=nkq2^{n_{k}}+2=n_{k} \cdot q, where qq is a positive odd number. Furthermore, let 2nk+1=(nk1)p2^{n_{k}}+1=\left(n_{k}-1\right) \cdot p, where pp is a positive odd number. We have
2nk+1+2=2(2nk+11+1)=2(2(nk1)p+1)=2(2nk1+1)M=(2nk+2)M=nk+1M\begin{aligned} 2^{n_{k+1}}+2 & =2\left(2^{n_{k+1}-1}+1\right)=2\left(2^{\left(n_{k}-1\right) p}+1\right)=2\left(2^{n_{k}-1}+1\right) M \\ & =\left(2^{n_{k}}+2\right) M=n_{k+1} \cdot M \end{aligned}

where MNM \in \mathbf{N}^{*} (by factorization). Thus, nk+1(2nk+1+2)n_{k+1} \mid\left(2^{n_{k+1}}+2\right).
On the other hand, we also have
2nk+1+1=2nkq+1=(2nk+1)N2^{n_{k+1}}+1=2^{n_{k} \cdot q}+1=\left(2^{n_{k}}+1\right) \cdot N

where NN is a positive integer. Thus, (nk+11)(2nk+1+1)\left(n_{k+1}-1\right) \mid\left(2^{n_{k+1}}+1\right). Therefore, the strengthened proposition holds.

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.