## Power of 2

What is the greatest power of 2 that divides 321024− 1?

[SOLVED]

#### Prunthaban Kanthakumar solved this puzzle:

Claim: 32n − 1 is divisible by 2n + 2 and not divisible by 2n + 3.

Proof:

Let f(n) = 32n.

Now f(n) − 1 = [f(n − 1) + 1][f(n − 1) − 1].   (Using the identity a2 − b2 = (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](23).

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 3n + 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 'x1012' (x1012 × x1012 = y10012); an introduction of a zero in the pattern or a left shift of the rightmost non-LSB one. Thus each square of the pattern 'x1012' results in an increment of the largest power of 2 that divides 'x1012 − 12'.

In our case 9 (10012) would be a good starting point to determine the largest factor that is a power of 2.

321 − 1 has 23 as the largest factor that is a power of 2.

Let 32n − 1 have 2m as the largest factor that is a power of 2.

32n × 32n = 32n + 2n = 32n + 1

So, 32n + 1 − 1 has 2m + 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, 21026 is the largest power of 2 that is a factor of 321024 − 1.

#### Mark Brader solved this puzzle:

21026.

Claim: 32N− 1 is a multiple of 2N + 2 but not of 2N + 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 = 32N− 1 and P = 2N + 2. We assume X is a multiple of P but not 2P, and we need to prove that 32N + 1− 1 is a multiple of 2P but not 4P.

32N− 1 = X

32N = X + 1

32N + 1 = (X + 1)2

32N + 1− 1 = X2 + 2X

By assumption X is a multiple of P. Therefore X2 is a multiple of P2. Since P is a power of 2 (greater than 4), P is divisible by 4 and therefore P2 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 X2 + 2X is a multiple of 2P but not 4P, qed.

#### Jonathan Krause solved this puzzle:

321024 − 1 = (321 − 1) · (Π1023i=1 32i + 1)

321 − 1 = 8 has three factors of 2.

Each 32i + 1 term has only one factor of 2 for i > 0.

For i = 1, 32i + 1 = 32 + 1 = 10. So, base case is true.

Induction: Let ni = 32i + 1. We have ni + 1 = (ni − 1)2 + 1. Now, let ni = 2mi, where mi is not divisible by 2 (true by induction hypothesis).

ni + 1 = (ni − 1)2 + 1 = (2mi − 1)2 + 1 = 4mi2 - 4mi + 1 + 1 = 4mi(mi − 1) + 2

4mi(mi − 1) is divisible by 4, so 4mi(mi − 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 21026.

### Credit

This puzzle is based on: