Number Theory - Concrete Mathematics 4.9 (2/10)

The text of the question is:

Show that the number $(3^{77}-1)/2$ is odd and composite.

The hint proposed in the question text is to compute $3^{77} \mod\  4$ (mod means division reminder: $ 13 \mod\ 5\ =\ 3$). Let's do that then. The useful think is that there is only a small number of possible reminders mod 4 (four exactly), so we if we calculate first, second, third etc. power of 3 we will have some cycle:
$ 3 \mod\ 4\ =\ 3$
$ 3^2 \mod\ 4\ =\ 1$
$ 3^3 \mod\ 4\ =\ 3$
$ 3^4 \mod\ 4\ =\ 1$
...
Bum! Pattern spotted. Therefore: $3^{77} \mod\  4\ =\ 3$. Now by simple transform:
$3^{77}-1 \mod\  4\ =\ 2$
$(3^{77}-1)/2 \mod\  2\ =\ 1$
So the number is odd. If any of above transformations confuses you please read about modular arithmetic. The prove that it's composite you have to know some of the less popular quick multiplication formulas:

In our case formula is a little simpler:

$a^n-1 = (a-1)(a^{n-1}+ .. + 1)$

Now how to use it? $a = 3$ gives factor of 2 but we divide by two in the formula, so that's not helpful, right?


Right? 


Wrong!


And I have to admit a fall for this a the beginning, but after consultation with a friend I went back on the right path:
Let's consider $ a = 3^{7}$. It gives us
$(3^7)^{11}-1 = (3^7-1)*((3^7)^{10} + (3^7)^9.. + 1)$
Where X is some integer greater than one. So then 
$( (3^{77}-1)/2 = (3^7-1)/2 * ((3^7)^{10} + (3^7)^9.. + 1) $,  so it's composite. Eureca!



OK. I have to admit this question was boring. I am sorry I picked up question at random just to write some test thing on blog. It was a little challenging but come on, who likes tedious arithmetic?