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

  • Thread starter Thread starter kaliprasad
  • Start date Start date
  • Tags Tags
    Remainder
AI Thread Summary
The remainder of \(3^{2^n} - 1\) when divided by \(2^{n+3}\) is \(2^{n+2}\). This conclusion is reached through mathematical induction, starting with the base case where \(n=1\), confirming that \(3^{2^1} - 1 = 8\) is an odd multiple of \(2^3\). The inductive step shows that \(3^{2^{n+1}} - 1\) can be expressed as the product of two factors, where the first is an odd multiple of \(2^{n+2}\) and the second is also an odd multiple of \(2\). The discussion highlights the clarity of the proof provided by a user named Opalg, which is appreciated by others in the thread. Overall, the mathematical reasoning is solid and effectively demonstrates the claim.
kaliprasad
Gold Member
MHB
Messages
1,333
Reaction score
0
find the remainder when $3^{2^n}-1$ is divided by $2^{n+3}$
 
Mathematics news on Phys.org
kaliprasad said:
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]
 
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 $$3^{2^n}-1$$ as $$9^n-1$$ and $$2^{n+3}$$ as $$8\cdot 2^n$$

?
 
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 $$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]
 
Bacterius said:
[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... :o:o:o
 
good solution by opalg
here is another
$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
 
Last edited:
Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
Back
Top