Maths Olympiad Prep

Library / /12 of 64

Number theory Difficulty 7.7 National olympiad, round 2 Find the answer

Find all positive integers n<10100n < 10^{100} for which simultaneously nn divides 2n2^n, n1n-1 divides 2n12^n-1, and n2n-2 divides 2n22^n - 2.

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

Solution

The values of nn with this property are 222^{2^\ell} for =1,2,4,8\ell = 1,2,4,8. First, note that nn divides 2n2^n if and only if nn is itself a power of 2; we may thus write n=2mn = 2^m and note that if n<10100n<10^{100}, then 2m=n<10100<(103)34<(210)34=2340. 2^m = n < 10^{100} < (10^3)^{34} < (2^{10})^{34} = 2^{340}. Moreover, the case m=0m=0 does not lead to a solution because for n=1n=1, n1=0n-1 = 0 does not divide 2n1=12^n-1 = 1; we may thus assume 1m3401 \leq m \leq 340. Next, note that modulo n1=2m1n-1 = 2^m-1, the powers of 22 cycle with period mm (the terms 20,,2m12^0, \dots, 2^{m-1} remain the same upon reduction, and then the next term repeats the initial 1); consequently, n1n-1 divides 2n12^n-1 if and only if mm divides nn, which happens if and only if mm is a power of 2. Write m=2m = 2^\ell and note that 2<340<5122^\ell < 340 < 512, so <9\ell < 9. The case =0\ell=0 does not lead to a solution because for n=2n=2, n2=0n-2 =0 does not divide 2n2=22^n-2 = 2; we may thus assume 181 \leq \ell \leq 8. Finally, note that n2=2m2n-2 = 2^m-2 divides 2n22^n-2 if and only if 2m112^{m-1} - 1 divides 2n112^{n-1} - 1. By the same logic as the previous paragraph, this happens if and only if m1m-1 divides n1n-1, that is, if 212^\ell - 1 divides 2m12^m-1. This in turn happens if and only if \ell divides m=2m = 2^\ell, which happens if and only if \ell is a power of 2. The values allowed by the bound <9\ell < 9 are =1,2,4,8\ell = 1,2,4,8; for these values, m28=256m \leq 2^8 = 256 and n=2m2256(23)86<1086<10100, n = 2^m \leq 2^{256} \leq (2^3)^{86} < 10^{86} < 10^{100}, so the solutions listed do satisfy the original inequality.

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