A few years ago

Number Theory Level 4

Find the smallest positive integer $n$ for which $3^{2^n}-1$ is divisible by $2^{1995}$ .

The answer is 1993.

2 solutions

Kazem Sepehrinia
Aug 13, 2015

$3^{2^n}-1=9^{2^{n-1}}-1$ Since $4|9-1$ using LTE lemma for $p=2$ we get $v_2(9^{2^{n-1}}-1)=v_2(9-1)+v_2(2^{n-1})=3+n-1=n+2$ Now we must have $1995|n+2$ , smallest such positive integer is $n=1993$ .

can you plz elaborate what is LTE

Aarabdh Tiwari - 5 years, 10 months ago

LTE lemma.

Kazem Sepehrinia - 5 years, 10 months ago

I've got 1994 but I found my error. I didn't consider that $3^{2^{0}} + 1 = 4$ and has two times 2 as a factor, so I need to reduce one more from my answer.

Gustavo Cardenas - 5 years, 9 months ago

using totient function, its n = 1994

Dev Sharma - 5 years, 10 months ago

Akshat Sharda
Sep 10, 2015

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$ .

Now we are given that $3^{2^{n}}-1$ must be divisible by $2^{1995}$ .

$\Rightarrow n+2=1995$

$\Rightarrow n=\boxed{1993}$

A few years ago

The answer is 1993.

2 solutions

0 pending reports