Divisibility Puzzle

Apply Lifting The Exponent Lemma (LTE):

$\upsilon_2\left(3^{1024}-1\right)=\upsilon_2(3-1)+\upsilon_2(3+1)+\upsilon_2(1024)-1$

$=1+2+10-1=\boxed{12}$

The reason LTE works is (basically its proof):

$3^{1024}-1=\left(3^{512}-1\right)\left(3^{512}+1\right)=\left(3^{256}-1\right)\left(3^{256}+1\right)\left(3^{512}+1\right)$

$=\cdots=(3-1)(3+1)\left(3^{2}+1\right)\left(3^{4}+1\right)\cdots\left(3^{512}+1\right)$

$3^{2}+1\equiv 3^{4}+1\equiv \cdots\equiv 3^{512}+1\equiv 2\pmod{4}$ ,

because $3^{2^k}+1\equiv (-1)^{2^k}+1\equiv 1+1\equiv 2\pmod{4}$ .

Therefore $\upsilon_2\left(3^{1024}-1\right)=\upsilon_2(3-1)+\upsilon_2(3+1)+\upsilon_2\left(3^2+1\right)+$

$+\upsilon_2\left(3^4+1\right)+\cdots+\upsilon_2\left(3^{512}+1\right)$

$=1+2+\underbrace{1+1+\cdots+1}_{9 \text{ times}}=12$

We can observe a pattern ,

$3^{2}-1 \Rightarrow$ divisible by $2^{3}$ .

$3^{4}-1 \Rightarrow$ divisible by $2^{4}$ .

$3^{8}-1 \Rightarrow$ divisible by $2^{5}$ .

.

.

.

So $3^{2^{n}}-1\Rightarrow$ divisible by $2^{n+2}$ when $n>0$ .

So $3^{2^{10}}-1$ is divisible by $2^{10+2}=2^{12}$

Answer : $\boxed{12}$

---

$\text{Applying LTE}\rightarrow$

$=\upsilon_{2}(3^{1024}-1)$

$=\upsilon_{2}(3-1)+\upsilon_{2}(3+1)+\upsilon_{2}(1024)-1$

$=1+2+10-1=\boxed{12}$

We can show by induction that the highest power of 2 dividing $3^{2^n}-1$ is $n+2$ , for $n>0$ . The case $n=1$ is trivial. For the induction step, write $3^{2^{n+1}}-1$ $=(3^{2^n}-1)(3^{2^n}+1)$ . The highest power of 2 dividing the first factor is assumed to be $n+2$ , and for the second factor it's 1 since $3^{2^n}+1\equiv2\pmod{4}$ .

For $n=10$ the highest power is $\boxed{12}$

3^1024 - 1 = 9^512 - 1 = (8 + 1)^512 - 1 = 8^512 + .... + C(512, 2) 8^2 + (512)8 + 1 - 1 = 2^1536 + ... + 511 2^14 + 2^12 = 2^12(4k + 1).

Hence 12 is the highest power of 2

using the LTE lemma, v2(3^1024 - 1) = v2(9^512 - 1) = v2(9 - 1) + v2(512) = 3 + 9 = 12. Therefore, 4096|(3^1024 - 1) but 8192 didn't, so 12 is the answer.