Maths Olympiad Prep

Library / /179 of 520

Number theory Difficulty 5.0 AIME, harder Find the answer

Example 10. (IMO-6-1) a) Find all positive integers nn such that 2n12^{\mathrm{n}}-1 is divisible by 7.
b) Prove that there is no positive integer nn such that 2n+12^{n}+1 is divisible by 7.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Solve α\alpha) First note that for k0,kk \geqslant 0, k an integer, 23k12^{3 k}-1 is divisible by 7. Proof as follows:

Since 231(mod7)2^{3} \equiv 1 \pmod{7}, it immediately follows that
23k1(mod7), which means 723k1 2^{3 k} \equiv 1 \pmod{7}, \text{ which means } 7 \mid 2^{3 k}-1 \text{. }
(Or, using 23k1=(23)k1=(231)2^{3 k}-1=\left(2^{3}\right)^{k}-1=\left(2^{3}-1\right)
- (23k3++1)\left(2^{3 k-3}+\cdots+1\right), we can also deduce this.)

Thus, 23k+11=2(23k1)+12^{3 k+1}-1=2\left(2^{3 k}-1\right)+1, 23k+21=4(23k1)+32^{3 k+2}-1=4\left(2^{3 k}-1\right)+3 cannot be divisible by 7.
Therefore, 2n12^{n}-1 is divisible by 7 if and only if 3n3 \mid n.
b) Since 23k1(mod7)2^{3 k} \equiv 1 \pmod{7}, it follows that 23k+12^{3 k}+1 \equiv 2(mod7),23k+1+13(mod7),23k+2+12 \pmod{7}, 2^{3 k+1}+1 \equiv 3 \pmod{7}, 2^{3 k+2}+1
5(mod7)\equiv 5 \pmod{7}. Hence, for any nNn \in \mathbb{N}, 7×2n+17 \times 2^{\mathbf{n}}+1.

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.