Results 1 to 4 of 4

Math Help - Show that this number is odd and composite

  1. #1
    Newbie
    Joined
    Mar 2010
    Posts
    8

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by asviola View Post
    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}).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
     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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Mar 2010
    Posts
    8
    Thankyou!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. composite number proof
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: September 7th 2010, 07:35 PM
  2. What's so special about this composite number
    Posted in the Number Theory Forum
    Replies: 33
    Last Post: May 5th 2010, 02:14 AM
  3. Show the limit of two composite functions aren't =
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: October 20th 2009, 05:42 PM
  4. rolling a composite number with one die
    Posted in the Statistics Forum
    Replies: 1
    Last Post: September 29th 2009, 01:19 PM
  5. Composite number proof help
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 6th 2007, 10:26 AM

Search Tags


/mathhelpforum @mathhelpforum