Finding remainder of dividing $3^{2^n}$ by $2^{n+3}$ Find the remainder of dividing $3^{2^n}$ by $2^{n+3}$
I was trying to use $ord_{2^{n+3}}(3)$, but i don't see a future in looking for a constant when I change the value of n. However, I was looking for a less advanced solution, is it possible?
 A: Here's a solution that uses the Lifting the Exponent Lemma (LTE).
Since $\varphi(2^n)=2^{n-1}$ we suspect that $3^{2^n}$ and $1$ are near each other. We can now apply the LTE, since we satisfy the criteria of $2|(3-1)$, with $2 \nmid 1$ and $2 \nmid 3$.
$$v_2(3^{2^n}-1^{2^n}) = v_2(2^n) + v_2(3-1) + v_2(3+1) - 1 = n+2$$
This means we have exactly $3^{2^n}-1 = 0 \mod 2^{n+2}$ with $3^{2^n}-1 \ne 0 \mod 2^{n+3}$. This must mean we have $3^{2^n}-1 = a2^{n+2} \mod 2^{n+3}$.
It is perhaps clearer to think of this as the base $2$ expansion of the number, and we have only two choices for $a$ - it can be $0$ or $1$. If it's $0$ we end up contradicting that $3^{2^n}-1 \ne 0 \mod 2^{n+3}$ from the LTE, so it must be that $a=1$.
A: You could show by induction that the remainder is $2^{n+2}+1$.
Base case ($n=1$):  $\;3^{2^n}=9=2^{n+2}+1\pmod {2^4=16}$.
Now assume $3^{2^n}\equiv 2^{n+2}+1\bmod 2^{n+3}$; i.e., $3^{2^n}=2^{n+2}+1+k\cdot2^{n+3}$ for some integer $k$.
Then $3^{2^{n+1}}=\left(3^{2^n}\right)^2=2^{2n+4}+1+k^2\cdot2^{2n+6}+2^{n+3}+k\cdot2^{2n+6}+k\cdot2^{n+4}$
$\equiv1+2^{(n+1)+2}\pmod{2^{(n+1)+3}}.$
