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$.
On
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$$
On
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$.
On
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$.
On
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}}$$
On
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}$
On
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$.
On
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}$$
$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.