# Show that $\frac{(3^{77}-1)}{2}$ is odd and composite

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.

-
In this case it's true that $(3^{77}-1)/2\equiv 1 \pmod{4}$, but observe that from $x\equiv 2 \pmod{4}$ it does not necessarily follow that $x/2 \equiv 1 \pmod{4}$, only that it is odd. – Zander Jun 9 '12 at 18:58

Hint: $$a^n-1=(a-1)(a^{n-1}+a^{n-2}+...+a+1)\,,\,\,\forall n\in\mathbb{N} \wedge \forall a\in\mathbb{R}$$

Added Of course, we also have in this case, applying the above: $$3^{77}-1=\left(3^7\right)^{11}-1=(3^7-1)\left(\left(3^7\right)^{10}+\left(3^7\right)^9+...+3^7+1\right)\,,\,etc.$$ and something similar can be done with $\,3^{77}=\left(3^{11}\right)^7$

-

Hint $\,$ The sought factors demonstrating compositeness of your number arise very simply from a compositional factorization $\rm\:g\:\!f = g\circ f\:$ of a polynomial, combined with the Factor Theorem.

$$\begin{eqnarray}\rm z\,\ -\,\ c\ & | &\,\rm\ g\:\!(\,z\,) - g\:\!(\,c\,) \\ \rm f(x)\!-\!f(a) &|&\,\rm\ g\:\!f(x) - g\:\!f(a) \\ \rm x^7\, -\, a^7\, & | &\,\rm (x^{7})^{11} - (a^{7})^{11} \\ 3^7-\,1\ & | &\:\!\ (3^{7})^{11} - 1 \end{eqnarray}$$

Note that if we employ the notation $\rm\:x^f = f(x)\:$ (e.g. as in Galois theory) then it is clearer

$$\begin{eqnarray}\rm z\,\ -\,\ c\,\:\! & | &\rm\ (\,z\,)^g - \:\!(\,c\,)^g \\ \rm x^f\ -\ a^f\, &|&\rm\ (x^f)^g - (a^f)^g \\ \rm x^7\, -\, a^7\, & | &\:\rm (x^{7})^{11}\!\! - (a^{7})^{11} \\ 3^7-\,1\ & | &\:\!\ (3^{7})^{11\!} - 1 \end{eqnarray}$$

In the Galois case the exponential notation highlights further structure, e.g. from my post here

\quad\quad\begin{align}{} \rm g^{\:\sigma^4-1} \;=\;& \rm g^{\:(1\:+\;\sigma\:+\;\sigma^2\:+\;\:\sigma^3)\:(\sigma-1)} \\\\ \iff\quad\quad\rm \frac{\sigma^4 g}g \;=\;& \rm (g \;\: \sigma\:g \;\:\sigma^2 g \;\:\sigma^3 g)^{\sigma - 1} \;=\; \frac{\phantom{g\;\;\:} \sigma\:g \;\;\: \sigma^2 g \;\;\:\sigma^3 g \;\;\:\sigma^4 g}{g \;\;\:\sigma\:g \;\;\:\sigma^2 g \;\;\:\sigma^3 g\phantom{\;\;\:\sigma^4 g}} \\\\ \end{align}

-

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.)

-
+1 for an interesting, creative method I would never have thought of! – Shaktal Jun 9 '12 at 19:24
+1 Ditto as above: beautiful! – DonAntonio Jun 9 '12 at 21:09

Well following your congruences idea we have that $$3^{77} \equiv 3^{11} \equiv 1 \pmod{23}$$ So $$3^{77} - 1\equiv 0 \pmod{23}$$ Since $2^{-1} \equiv 12 \pmod{23}$, we have that $$\dfrac{3^{77}-1}{2} \equiv 0 \pmod{23}$$ Hence $23 \mid \dfrac{3^{77}-1}{2}$ and is therefore composite.

-
That's an interesting method, can I ask where the number $23$ came from though? – Shaktal Jun 9 '12 at 16:35
Trial and error sadly. – Eugene Jun 9 '12 at 16:36
Or if not trial and error, then Little Fermat telling us that $$3^{22}\equiv1\pmod{23}$$ together with $$3^{77}=3^{11+22\cdot3}\equiv3^{11}\cdot(3^{22})^3\equiv3^{11}\pmod{23}.$$ – Jyrki Lahtonen Jun 9 '12 at 16:43
@JyrkiLahtonen Yes Fermat's Little Theorem was the idea behind the trial and error. That only gets you so far though... – Eugene Jun 10 '12 at 0:40
Given the hints in the question, you could just look at $\frac{(3^{11}-1)}{2} = 88573 = 23 \times 3851$ while $\frac{(3^{7}-1)}{2} = 1093$ is prime. – Henry Jun 10 '12 at 8:21

Note the algebraic factorisation:

$x^{nm} - 1 = (x^m - 1)(x^{m(n-1)} + x^{m(n-2)} + ... + x^m + 1)$

If we let $x=3, m=7, n=11$ then we see that $3^7 - 1$ divides $3^{77} - 1$.

So $\frac{3^{77} - 1}{2} = \frac{3^7 - 1}{2}k$ for some integer k as required.

-

Note that if $m=kn$ for some $k\in\mathbb{N}$, then $$a^m-1=(a^n)^k-1=(a^n-1)(a^{n(k-1)}+a^{n(k-2)}+\cdots+a^n+1)$$ so that $a^n-1$ divides $a^m-1$.

-