Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

6 Answers 6

up vote 11 down vote accepted

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$

share|improve this answer
add comment

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

share|improve this answer
    
+1 for an interesting, creative method I would never have thought of! –  Shaktal Jun 9 '12 at 19:24
3  
+1 Ditto as above: beautiful! –  DonAntonio Jun 9 '12 at 21:09
add comment

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.

share|improve this answer
2  
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
1  
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
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.