12
$\begingroup$

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.

  • 0
    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.2012-06-09

6 Answers 6

3

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.

24

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

  • 0
    +1 for an interesting, creative method I would never have thought of!2012-06-09
10

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$

6

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.

  • 0
    @Eugene *Please correct me if I am wrong:* You said, "Since $2^{-1} \equiv 12 \pmod{23}$...". Instead of noticing that, you could have just divided $3^{77}-1$ by $2$ as $\gcd(23,2)=1$.2014-11-05
4

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

4

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