Showing that $2^6$ divides $3^{2264}-3^{104}$ 
Show that $3^{2264}-3^{104}$ is divisible by $2^6$. 

My attempt: Let $n=2263$. Since $a^{\phi(n)}\equiv 1 \pmod n$ and
$$\phi(n)=(31-1)(73-1)=2264 -104$$
we conclude that $3^{2264}-3^{104}$ is divisible by $2263$. 
I have no idea how to show divisibility by $2^6$.
 A: Note that
$$3^{2264}-3^{104}=3^{104}\cdot (3^{2160}-1)$$
and $\gcd(2,3)=1$, so $64$ divides this number if and only if it divides the factor $3^{2160}-1$. Since 
$$3^{2160}-1=(3^{16})^{135}-1$$
and $3^{16}\equiv 1\bmod 64$, we have that $(3^{16})^{135}\equiv 1^{135}\equiv 1\bmod 64$ and therefore $64\mid (3^{16})^{135}-1$.
A: You've got $(3^{2160} - 1)\cdot3^{104}$.
The second half of that is obviously not divisible by $2$, so we must show that $3^{2160} \equiv 1\ (\text{mod}\ 2^6)$.
A quick brute force check of exponents of $3$ gives $3^{16} \equiv 1\ (\text{mod}\ 64)$; $2160=16 \times 135$.
A: Since $2264-104=2160=2^4\cdot 135$, we can write
$$3^{2264}-3^{104}=3^{104}(3^{1080}+1)(3^{540}+1)(3^{270}+1)(3^{135}+1)(3^{135}-1)$$
Here, note that 
$$3^{n}\pm1\equiv 0\pmod 2$$
and that
$$3^{135}+1\equiv (-1)^{135}+1\equiv 0\pmod 4$$
A: A variant with some details:
By *Euler's theorem, $\;3^{\varphi(2^6)}\equiv 3^{32}\equiv=1\mod 2^6$. So
$$3^{2264}-3{104}\equiv3^{2264\bmod\varphi(2^6)}-3^{104\bmod\varphi(2^6)}\equiv 3^{24}-3^{8}\equiv3^8(3^{16}-1)\mod 2^6,$$
so it is enough to prove $3$ has order $16$ mod $2^6=64$. 
Let's use the fast exponentiation algorithm mod $64$:
$$\begin{array}{r| l}
k & 3^k \\\hline
1&3\\2&9\\4&81\equiv 17\\8&289 \equiv-31\\16&961\equiv\color{red}{1}
\end{array}$$
A nicer and faster computation (after @Joffan's suggestion):
As $x\equiv a\mod 2^k\implies x^2\equiv a^2\mod 2^{k+1}$, we have
$$ 3 \equiv -1\mod 2^2\implies3^2 \equiv 1\mod2^3,$$
whence $3^{16}\equiv 1\mod 2^6$.
A: Another approach:
$$\text{Euler's formula:  }\quad a^{\phi(n)}\equiv 1 \pmod{n} \text{ when} \gcd(a,n)=1$$
$\implies a^{32}\equiv 1 \pmod{2^6}$
We want $3^{2264}-3^{104}\equiv 0 \pmod{2^6}$
$$\phi(2^6)=2^5=32$$
$$ 3^{2264}-3^{104}=3^{2240}3^{24}-3^{96}3^{8}=(3^{70})^{32}3^{24}-(3^3)^{32}3^8\equiv 3^{24}-3^8\equiv 17^6-17^2\\
\equiv 33^3-33\equiv \color{green}{0 \pmod{2^6}}$$
A: $3^{2264}-3^{104} = 3^{104}(3^{2160}-1)$
$\lambda(2^6) = 2^4 = 16$ where $\lambda$ is the Carmichael  or reduced totient function
$16 \mid 2160 \implies 3^{2160}\equiv 1 \bmod 2^6 \implies 2^6 \mid (3^{2160}-1)$
and $2^6$ divides $3^{2264}-3^{104}$ as required.
A: If Euler/Carmichael are unfamiliar, we can instead use the Binomial Theorem 
$\ {\rm mod}\ 8^2\!:\,\ \color{#c00}{3^{\large 16}}\equiv 9^{\large 8}\equiv (1\!+\!8)^{\large\color{#0a0} 8}\equiv 1 + \color{#0a0}8\cdot 8 + 8^2(\cdots)\equiv \color{#c00}{\bf 1}$
therefore $\ \ 3^{\large J+16K} - 3^{\large J} \equiv\, 3^{\large J}(\color{#c00}3^{\large\color{#c00}{16}K} - 1)\,\equiv\, 3^{\large J}(\color{#c00}{\bf 1}^{\large K}-1)\equiv 0\,\pmod{8^2}$
A: Just to give another way (all the answers, including mine, are equivalent I guess) and expose
the division is exact (i.e. $2^7$ does not divide $3^{2264}-3^{104}$).
$$3^{2264}-3^{104}=3^{104}(3^{2160}-1)=3^{104}(3^{1080}-1)(3^{1080}+1)=3^{104}(3^{8\cdot135}-1)(3^{8\cdot135}+1)=\\=3^{104}(6561^{135}-1)(6561^{135}+1)=\text{odd}(6560\cdot odd)(6562\cdot odd )$$ (because the factors of $6561-1=6560$ and $6561+1=6562$ are both a sum of an odd number of odd terms). It follows because of $6560=2^5\cdot5\cdot41$ and $6562=2\cdot17\cdot193$ that
$$3^{2264}-3^{104}
=\color{red}{\text{odd}\cdot2^6}$$
