- #1
kaliprasad
Gold Member
MHB
- 1,335
- 0
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}$.kaliprasad said:find the remainder when $3^{2^n}-1$ is divided by $2^{n+3}$
DreamWeaver said: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...
write \(\displaystyle 3^{2^n}-1\) as \(\displaystyle 9^n-1\) and \(\displaystyle 2^{n+3}\) as \(\displaystyle 8\cdot 2^n\)
?
Bacterius said:[sp]$$3^{2^n} = 3^{(2^n)} \ne (3^2)^n = 3^{2n} = 9^n$$[/sp]
The formula for calculating the remainder is $3^{2^n}-1 \equiv 2^{n+2} \pmod{2^{n+3}}$.
The number $2^{n+3}$ represents the divisor or the number that we are dividing the original expression, $3^{2^n}-1$, by. It is important because it determines the size of the remainder and plays a crucial role in the calculation.
We can prove this using mathematical induction. The base case, when $n=0$, is trivial as both the remainder and $2^{n+2}$ equal 2. For the inductive step, assume that the formula holds for $n=k$, then we can show that it also holds for $n=k+1$. This can be done by substituting $n=k+1$ into the formula and using the fact that $3^{2^{k+1}}-1 = (3^{2^{k}}-1)(3^{2^{k}}+1)$. By the inductive hypothesis, we know that the remainder of $3^{2^{k}}-1$ divided by $2^{k+3}$ is $2^{k+2}$, which when multiplied by 3, gives us $2^{k+3}$, the desired remainder.
Yes, this formula can be generalized for any base number. In general, the remainder of $a^{2^n}-1$ divided by $2^{n+3}$ is $2^{n+2}$, where a is any positive integer greater than 1.
This formula has various applications in computer science and cryptography. In computer science, it is used in programming languages to efficiently compute large powers of numbers. In cryptography, it is used in the RSA encryption algorithm to calculate the private key from the public key. It also has applications in number theory and modular arithmetic.