# Math Help - Show that this number is odd and composite

1. ## Show that this number is odd and composite

Show the (3^77-1)/2 is odd and composite.

(Hint: consider 3^77mod4 and the formula a^n-b^n=(a-b)(a^(n-1)+a^(n-2)*b+...+a*b^(n-2)+b^(n-1)) for any positive integers a, b, n).

I rewrote (3^77-1) as (3^77-1^77) and then in the form given in the hint, which when simplified turns the number into 3^76+3^75+...+3^1+3^0, but I'm not sure where to go from there, or how 3^77mod4 is useful.

2. Originally Posted by asviola
Show the (3^77-1)/2 is odd and composite.

(Hint: consider 3^77mod4 and the formula a^n-b^n=(a-b)(a^(n-1)+a^(n-2)*b+...+a*b^(n-2)+b^(n-1)) for any positive integers a, b, n).

I rewrote (3^77-1) as (3^77-1^77) and then in the form given in the hint, which when simplified turns the number into 3^76+3^75+...+3^1+3^0, but I'm not sure where to go from there, or how 3^77mod4 is useful.
The expression $3^{76}+3^{75}+\ldots+3^1+3^0$ is a sum of 77 odd numbers, so is odd (and if you do the question that way, you don't need the hint about mod 4).

To see that the number is composite, notice that the identity $a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+\ldots+ab^{n-2}+b^{n-1})$ tells you that $(a^7)^{11} - (b^7)^{11} = (a^7-b^7)(a^{70} + a^{63}b^7 + \ldots + a^7b^{63} + b^{70})$.

3. $3^{77} \equiv (-1)^{77} = -1 \mod{4} \implies 3^{77} = 4k+3$.

Therefore $\frac{3^{77}-1}{2} = \frac{4k+3-1}{2} = \frac{4k+2}{2} = 2k+1$.

Hence $\frac{3^{77}-1}{2}$ is odd.

4. Thankyou!