Remainder of $3^{2^n}-1$ Divided by $2^{n+3}$

[kaliprasad]

find the remainder when $3^{2^n}-1$ is divided by $2^{n+3}$

 

[Opalg]

find the remainder when $3^{2^n}-1$ is divided by $2^{n+3}$

[sp]Claim: $3^{2^n}-1$ is an odd multiple of $2^{n+2}$.

Proof by induction: Base case ($n=1$) is true because $3^{2^1}-1 = 3^2-1 = 8$, which is an odd multiple of $2^{1+2} = 2^3 = 8.$ For the inductive step, $3^{2^{n+1}} - 1 = (3^{2^n}-1) (3^{2^n}+1)$ (difference of two squares). By the inductive hypothesis, the first factor is an odd multiple of $2^{n+2}$. The second factor is $(3^{2^n}-1) + 2$ which, again by the inductive hypothesis, is an odd multiple of $2$. Therefore the product $3^{2^{n+1}} - 1$ of the two factors is an odd multiple of $2^{n+3}$, which completes the inductive step.

It follows that the remainder when $3^{2^n}-1$ is divided by $2^{n+3}$ is $2^{n+2}$.[/sp]

 

[DreamWeaver]

It's been over a decade since I've done these kinds of problems on a regular basis - and I can't top Opalg's delicious proof above (nicely done! (Sun) ) - but I'm just wondering, would it not be easier if you were to...

Spoiler

write $$3^{2^n}-1$$ as $$9^n-1$$ and $$2^{n+3}$$ as $$8\cdot 2^n$$

?

 

[Nono713]

It's been over a decade since I've done these kinds of problems on a regular basis - and I can't top Opalg's delicious proof above (nicely done! (Sun) ) - but I'm just wondering, would it not be easier if you were to...

Spoiler

write $$3^{2^n}-1$$ as $$9^n-1$$ and $$2^{n+3}$$ as $$8\cdot 2^n$$

?

[sp]$$3^{2^n} = 3^{(2^n)} \ne (3^2)^n = 3^{2n} = 9^n$$[/sp]

 

[DreamWeaver]

[sp]$$3^{2^n} = 3^{(2^n)} \ne (3^2)^n = 3^{2n} = 9^n$$[/sp]

Egg on face! Ha ha! Thanks for that... I don't know what I was thinking there...

 

[kaliprasad]

good solution by opalg
here is another

Spoiler

$3^{2^n} - 1 = (3^{2^{n-1}} +1) (3^{2^{n-1}} -1)$
= $(3^{2^{n-1}} +1) (3^{2^{n-2}} +1)(3^{2^{n-2}} -1$
= $(3^{2^{n-1}} +1) (3^{2^{n-2}} +1)\cdots(3^2+1)(3^2-1)$

now there are 1st n-1 terms of the form $3^{2^k} + 1 $ where k = n-1 to 1

$3^{2^ k} - 1 = 3^{2x} - 1 = 9^x - 1$ as $2^k$ is even so

$3^{2^k} -1 \mod 4 = 0$

$3^{2^k} +1 \mod 4 = 2$

so $3^{2^k} +1 = 4 m + 2 = 2(2m+ 1)$

there are n-1 numbers of the form 2(2m+1) and last number is 8.
so product = $8 * 2^{n-1} * (2y + 1) = y . 2^{n+3} + 2 ^{n+2}$

so $product \mod 2^{n+3} = 2 ^{n+2}$

hence $2^{n+2}$ is the desired remainder