# Show that this number is odd and composite

• Mar 9th 2010, 11:05 PM
asviola
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.
• Mar 10th 2010, 06:39 AM
Opalg
Quote:

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})$.
• Mar 10th 2010, 02:01 PM
chiph588@
$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.
• Mar 11th 2010, 04:12 AM
asviola
Thankyou!