What is the greatest power of 2 that divides 3^{21024}− 1?

Sunday, August 21, 2011

Please email your solutions to puzzles@cotpi.com.

### 4 comments

### Credit

This puzzle is based on:

- Andreescu, Titu; Andrica, Dorin; Feng, Zuming. 104 Number Theory Problems: From the Training of the USA IMO Team. Boston: Birkhäuser, 2007. p. 9. Example 1.10.

## Prunthaban Kanthakumar solved this puzzle:

Answer: 2

^{1026}Claim: 3

^{2n}− 1 is divisible by 2^{n + 2}and not divisible by 2^{n + 3}.Proof:

Let f(n) = 3

^{2n}.Now f(n) − 1 = [f(n − 1) + 1][f(n − 1) − 1]. (Using the identity a

^{2}− b^{2}= (a + b)(a − b))By repeated expansion,

f(n) − 1 = [f(n − 1) + 1][f(n − 2) + 1]…[f(1) + 1][f(0) + 1][f(0) − 1].

f(n) − 1 = [f(n − 1) + 1][f(n − 2) + 1]…[f(1) + 1](4)(2).

f(n) − 1 = [f(n − 1) + 1][f(n − 2) + 1]…[f(1) + 1](2

^{3}).Now if we prove f(n) + 1 is divisible by 2 exactly once (for n > 0), then the maximum power of 2 dividing f(n) − 1 would simply be 3 + (n − 1). This is trivial. We know f(n) + 1 is divisible by 2 because 3

^{n}+ 1 is divisible by 2 for any non-negative integer n. Now out of f(n) − 1 and f(n) + 1 only one could be divisible by 4. We already know from above that f(n) − 1 is divisible by 4 for n > 0. So f(n) + 1 is not divisible by 4.This completes the proof.

## Rajesh Balakrishnan solved this puzzle:

In binary multiplication the following can be observed while doing a square of the pattern '

x101_{2}' (x101_{2}×x101_{2}=y1001_{2}); an introduction of a zero in the pattern or a left shift of the rightmost non-LSB one. Thus each square of the pattern 'x101_{2}' results in an increment of the largest power of 2 that divides 'x101_{2}− 1_{2}'.In our case 9 (1001

_{2}) would be a good starting point to determine the largest factor that is a power of 2.3

^{21}− 1 has 2^{3}as the largest factor that is a power of 2.Let 3

^{2n}− 1 have 2^{m}as the largest factor that is a power of 2.3

^{2n}× 3^{2n}= 3^{2n + 2n}= 3^{2n + 1}So, 3

^{2n + 1}− 1 has 2^{m + 1}as the largest factor that is a power of 2.For each increase in n, m also increases. So, m = n + 2 consistently.

Therefore, 2

^{1026}is the largest power of 2 that is a factor of 3^{21024}− 1.## Mark Brader solved this puzzle:

2

^{1026}.Claim: 3

^{2N}− 1 is a multiple of 2^{N + 2}but not of 2^{N + 3}, for all integers N > 0.Proof by mathematical induction follows.

Base step: N = 1. 8 is a multiple of 8 but not of 16.

Induction step: Let X = 3

^{2N}− 1 and P = 2^{N + 2}. We assume X is a multiple of P but not 2P, and we need to prove that 3^{2N + 1}− 1 is a multiple of 2P but not 4P.3

^{2N}− 1 = X3

^{2N}= X + 13

^{2N + 1}= (X + 1)^{2}3

^{2N + 1}− 1 = X^{2}+ 2XBy assumption X is a multiple of P. Therefore X

^{2}is a multiple of P^{2}. Since P is a power of 2 (greater than 4), P is divisible by 4 and therefore P^{2}is divisible by 4P.By assumption X is a multiple of P but not 2P. Therefore 2X is a multiple of 2P but not 4P.

Therefore X

^{2}+ 2X is a multiple of 2P but not 4P, qed.## Jonathan Krause solved this puzzle:

3

^{21024}− 1 = (3^{21}− 1) · (Π^{1023}_{i=1}3^{2i}+ 1)3

^{21}− 1 = 8 has three factors of 2.Each 3

^{2i}+ 1 term has only one factor of 2 for i > 0.For i = 1, 3

^{2i}+ 1 = 3^{2}+ 1 = 10. So, base case is true.Induction: Let n

_{i}= 3^{2i}+ 1. We have n_{i + 1}= (n_{i}− 1)^{2}+ 1. Now, let n_{i}= 2m_{i}, where m_{i}is not divisible by 2 (true by induction hypothesis).n

_{i + 1}= (n_{i}− 1)^{2}+ 1 = (2m_{i}− 1)^{2}+ 1 = 4m_{i}^{2}- 4m_{i}+ 1 + 1 = 4m_{i}(m_{i}− 1) + 24m

_{i}(m_{i}− 1) is divisible by 4, so 4m_{i}(m_{i}− 1) + 2 is not divisible by 4, though it is clearly divisible by 2.End of induction.

There are 3 factors of 2 from the 8, and 1 factor of 2 from each of the 1023 terms in the product. So, we get 2

^{1026}.