Results 1 to 5 of 5

Math Help - Show that (3k + 1)^9 ≡ 1 (mod 27)

  1. #1
    Junior Member
    Joined
    Nov 2011
    Posts
    30

    Show that (3k + 1)^9 ≡ 1 (mod 27)

    I know that 1 (mod 27) ≡ K implies that K = 27a + 1 where a is an integer.

    Thus I must show that (3k+1)^9 can turn out in that way. But the power is 9, that's a lot!!! Isn't there an easier way to show this?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21

    Re: Show that (3k + 1)^9 ≡ 1 (mod 27)

    Quote Originally Posted by SweatingBear View Post
    I know that 1 (mod 27) ≡ K implies that K = 27a + 1 where a is an integer.

    Thus I must show that (3k+1)^9 can turn out in that way. But the power is 9, that's a lot!!! Isn't there an easier way to show this?
    Here's how I think the best way to go about this is. Note that (3k+1,27)=1 and so by Euler's theorem this implies that (3k+1)^{\varphi(27)}=(3k+1)^{18}\equiv1\text{ mod }27. This tells us that x^2=1\text{ mod }27 where x=(3k+1)^{9}. From this we may conclude that (3k+1)^9\equiv \pm a\text{ mod }27. Now, why is (3k+1)^9\not\equiv-1\text{ mod }27?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,150
    Thanks
    591

    Re: Show that (3k + 1)^9 ≡ 1 (mod 27)

    another way is to use the binomial theorem...now, i know what you're thinking...that's a lot of calculation, but:

    every term is going to be of the form a(3k)^n. all the terms for n > 2 are going to disappear since (3k)^3 = (27)(k^3) = 0 (mod 27).

    so that leaves just the 9k^2, 3k and constant term.

    the constant term is going to be 1^9 = 1.

    the coefficient of the 3k term is going to be 9, and 9(3k) = 27k = 0 (mod 27).

    the coefficient of the (3k)^2 term is going to be 9!/(2!7!) = (8)(9)/2 = 36, and (36)(3k)^2 = (27)(4k^2) = 0 (mod 27),

    so only the constant term survives, and that's 1.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Nov 2011
    Posts
    30

    Re: Show that (3k + 1)^9 ≡ 1 (mod 27)

    Quote Originally Posted by Deveno View Post
    another way is to use the binomial theorem...now, i know what you're thinking...that's a lot of calculation, but:

    every term is going to be of the form a(3k)^n. all the terms for n > 2 are going to disappear since (3k)^3 = (27)(k^3) = 0 (mod 27).

    so that leaves just the 9k^2, 3k and constant term.

    the constant term is going to be 1^9 = 1.

    the coefficient of the 3k term is going to be 9, and 9(3k) = 27k = 0 (mod 27).

    the coefficient of the (3k)^2 term is going to be 9!/(2!7!) = (8)(9)/2 = 36, and (36)(3k)^2 = (27)(4k^2) = 0 (mod 27),

    so only the constant term survives, and that's 1.
    Starting to make a bit more sense, but the assumptions that you are making or evincing are not as obvious to me as they are to you. Could you please explain the middle steps a bit more thoroughly? Thank you for clearing things up!!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    -1
    e^(i*pi)'s Avatar
    Joined
    Feb 2009
    From
    West Midlands, England
    Posts
    3,053
    Thanks
    1

    Re: Show that (3k + 1)^9 ≡ 1 (mod 27)

    Quote Originally Posted by SweatingBear View Post
    Starting to make a bit more sense, but the assumptions that you are making or evincing are not as obvious to me as they are to you. Could you please explain the middle steps a bit more thoroughly? Thank you for clearing things up!!
    The binomial theorem is (1+\phi)^n = \sum_{k=0}^n {n \choose k}\phi^k

    In your case \phi = 3x

    (1+3x)^9 =

    1 + {9 \choose 1}(3x)^1 + {9 \choose 2}(3x)^2 + {9 \choose 3}(3x)^3 + {9 \choose 4}(3x)^4 + {9 \choose 5}(3x)^5 +{9 \choose 6}(3x)^6
     + {9 \choose 7}(3x)^7+ {9 \choose 8}(3x)^8 + (3x)^9

    Also note that a^b = a^{c+d} = a^ca^d given that b = c+d

    In our case take note that for each term above {9 \choose 2}(3x)^2 the exponent can be expressed as

    {9 \choose k}(3x)^{3+k} which, due to the law of exponents is the same as {9 \choose k}(3x)^3(3x)^k (where k is a non-negative integer)

    We also know from our laws of exponents that (3x)^3 = 27x^3 and so each term which has a (3x)^n term where n \geq 3 will be a multiple of 27.

    If a number is a multiple of 27 then it is 0(\mod 27)

    This means that each term above {9 \choose 2}(3x)^2 will be 0(\mod 27) (because they're all multiples of 27) and we're simply adding 0 after the third term.

    Therefore we look at our first two terms 1 + {9 \choose 1}(3x)^1 + {9 \choose 2}(3x)^2 = 1 + 9(3x) + 36(9x^2) = 1 + 27x + 324x^2

    You can then take those terms to mod 27 and be left with the constant. Does that make more sense?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Show that (3k+1)^3 ≡ 1 (mod 9)
    Posted in the Algebra Forum
    Replies: 4
    Last Post: November 6th 2011, 01:56 PM
  2. a ≡ b ?
    Posted in the Algebra Forum
    Replies: 1
    Last Post: May 7th 2011, 01:06 AM
  3. Replies: 0
    Last Post: June 28th 2010, 08:32 PM
  4. a^p≡1 (mod p^n) iff a≡1 (mod p^(n-1)), n≥2
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: March 8th 2010, 08:59 AM
  5. lcm of k,k+1,k+2 where k≡3(mod 4)
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: February 12th 2010, 01:46 PM

Search Tags


/mathhelpforum @mathhelpforum