The question given to me is:
Show that $\large\frac{(3^{77}-1)}{2}$ is odd and composite.
We can show that $\forall n\in\mathbb{N}$:
$$3^{n}\equiv\left\{
\begin{array}{l l}
1 & \quad \text{if $n\equiv0\pmod{2}$ }\\
3 & \quad \text{if $n\equiv1\pmod{2}$}\\
\end{array} \right\} \pmod{4}$$
Therefore, we can show that $3^{77}\equiv3\pmod{4}$. Thus, we can determine that $(3^{77}-1)\equiv2\pmod{4}$. Thus, we can show that $\frac{(3^{77}-1)}{2}$ is odd as:
$$\frac{(3^{77}-1)}{2}\equiv\pm1\pmod{4}$$
However, I am unsure how to show that this number is composite. The book I am reading simply states two of the factors, $\frac{(3^{11}-1)}{2}$ and $\frac{(3^{7}-1)}{2}$, but I do not know how the authors discovered these factors.
I'd appreciate any help pointing me in the right direction, thanks.
Best Answer
Another way to see this is by writing the number in base 3:
$$3^{77}=1\underbrace{00\dots00}_{77}\ _3$$
Here the index $3$ denotes base 3, and $77$ is the number of digits. Subtracting one, we get:
$$3^{77}-1=\underbrace{22\dots22}_{77}\ _3$$
Therefore, dividing this by two,
$$\frac{3^{77}-1}{2}=\underbrace{11\dots11}_{77}\ _3$$
From this we can directly read that the number is odd, since it is the sum of 77 odd numbers, and composite, since $$\underbrace{11\dots11}_{77}\ _3=1111111_3\cdot\underbrace{10000001000000\dots100000010000001}_{71}\ _3$$
(Although, this is basically the same as some of the other answers.)