Page 1 of 2 12 LastLast
Results 1 to 15 of 17

Math Help - Euler's theorem problem

  1. #1
    Newbie
    Joined
    Dec 2010
    Posts
    10

    Euler's theorem problem

    If n = 3^{x-1}, prove 2^n is congruent to -1 (mod 3^x).

    I think I should use Euler's Theorem for this but I'm not sure. Thanks for any help!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Nov 2010
    Posts
    58
    Thanks
    18
    Quote Originally Posted by Arzx View Post
    If n = 3^{x-1}, prove 2^n is congruent to -1 (mod 3^x).

    I think I should use Euler's Theorem for this but I'm not sure. Thanks for any help!
    Euler's Theorem states that if (a,m) = 1, then

    a^{\phi(m)} \equiv 1 (mod\ m)

    What do you get if you plug in a = 2 and m = 3^x? Can you use that congruence to solve the problem?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2010
    Posts
    10
    Quote Originally Posted by Petek View Post
    Euler's Theorem states that if (a,m) = 1, then

    a^{\phi(m)} \equiv 1 (mod\ m)

    What do you get if you plug in a = 2 and m = 3^x? Can you use that congruence to solve the problem?
    If I plug in those values, I get that 2^{3^{x} -1} \equiv 1 (mod\ 3^x), (I think). But it needs to be congruent to negative 1, so I'm not sure how to fix that. I know congruence-wise -1 is the same as 3^x -1 but that doesn't help does it?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Nov 2010
    Posts
    58
    Thanks
    18
    Quote Originally Posted by Arzx View Post
    If I plug in those values, I get that 2^{3^{x} -1} \equiv 1 (mod\ 3^x), (I think). But it needs to be congruent to negative 1, so I'm not sure how to fix that. I know congruence-wise -1 is the same as 3^x -1 but that doesn't help does it?
    Take another look at your congruence. If p is a prime and k is a positive integer, then

    \phi(p^k) = (p - 1)p^{k-1}
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Dec 2010
    Posts
    10
    Quote Originally Posted by Petek View Post
    Take another look at your congruence. If p is a prime and k is a positive integer, then

    \phi(p^k) = (p - 1)p^{k-1}
    Yikes, ok, so then I get that (2^2)(2^{3^{x -1}}) \equiv 1 (mod\ 3^x)? Where do I go from there?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Nov 2010
    Posts
    58
    Thanks
    18
    Quote Originally Posted by Arzx View Post
    Yikes, ok, so then I get that (2^2)(2^{3^{x -1}}) \equiv 1 (mod\ 3^x)? Where do I go from there?
    You made a simple algebra error with exponents. Your congruence should be

    (2^{2\cdot 3^{x -1}}) \equiv 1 (mod\ 3^x)

    Write this as

    (2^{3^{x -1}})^2} \equiv 1 (mod\ 3^x)

    and go from there.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Dec 2010
    Posts
    10
    Quote Originally Posted by Petek View Post
    You made a simple algebra error with exponents. Your congruence should be

    (2^{2\cdot 3^{x -1}}) \equiv 1 (mod\ 3^x)

    Write this as

    (2^{3^{x -1}})^2} \equiv 1 (mod\ 3^x)

    and go from there.
    Oops! Thanks for leading me through this.
    So I have (2^{3^{x -1}})^2} \equiv 1 (mod\ 3^x),
    which implies that either (2^{3^{x -1}}) \equiv 1 (mod\ 3^x) or  \equiv -1 (mod\ 3^x) .
    But, it can't be 1 because that would mean  (2^{3^{x -1}}) \equiv (2^{3^{x -1}})^2} ? Is that the right reasoning?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Banned
    Joined
    Nov 2010
    Posts
    58
    Thanks
    18
    Signing off for the day. Will reply tomorrow. You're getting close!
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Dec 2010
    Posts
    10
    Quote Originally Posted by Arzx View Post
    I have (2^{3^{x -1}})^2} \equiv 1 (mod\ 3^x),
    which implies that either (2^{3^{x -1}}) \equiv 1 (mod\ 3^x) or  \equiv -1 (mod\ 3^x)
    From here, I'm still not solid on why it must be -1 and not 1. I don't think saying      (2^{3^{x -1}}) \equiv (2^{3^{x -1}})^2} is really the correct idea, but I don't know what it is.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Banned
    Joined
    Nov 2010
    Posts
    58
    Thanks
    18
    which implies that either (2^{3^{x -1}}) \equiv 1 (mod\ 3^x) or  \equiv -1 (mod\ 3^x) .
    This implication isn't correct. It's true that if a prime divides a product of two numbers, then it must divide at least one of them. The same isn't true, however, for prime powers. For example, 3^2|6 \cdot 15, but 9 doesn't divide either factor.

    This point is the crux of the problem. Please think about it. Write out some examples for small values of x. Try to figure out, using the hints already given, why 3^x must divide (2^{3^{x-1}}) + 1.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Dec 2010
    Posts
    10
    Quote Originally Posted by Petek View Post
    This implication isn't correct. It's true that if a prime divides a product of two numbers, then it must divide at least one of them. The same isn't true, however, for prime powers. For example, 3^2|6 \cdot 15, but 9 doesn't divide either factor.

    This point is the crux of the problem. Please think about it. Write out some examples for small values of x. Try to figure out, using the hints already given, why 3^x must divide (2^{3^{x-1}}) + 1.
    Hmmm...OK.
    If x=1, then 3^1 does divide (2^{1}) + 1 (3/3)
    If x =2, then 3^2 does divide (2^{3}) + 1 (9/9)

    Is the reason because 2 \equiv -1 (mod\ 3)? Sorry, I'm still not sure what to do.
    Last edited by Arzx; December 7th 2010 at 04:23 PM.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Banned
    Joined
    Nov 2010
    Posts
    58
    Thanks
    18
    Not quite right, but closer. It's true that 2 \equiv -1 (mod\ 3), but that only implies that (2^{3^{x -1}})} \equiv -1 (mod\ 3), not (mod\ 3^x).

    You know that {3^{x -1}} divides the product ((2^{3^{x -1}})} +1)((2^{3^{x-1}}) - 1). Can you prove that 3 does not divide the second factor? If so, do you see why that solves the problem?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by Petek View Post
    Not quite right, but closer. It's true that 2 \equiv -1 (mod\ 3), but that only implies that (2^{3^{x -1}})} \equiv -1 (mod\ 3), not (mod\ 3^x).

    You know that {3^{x -1}} divides the product ((2^{3^{x -1}})} +1)((2^{3^{x-1}}) - 1). Can you prove that 3 does not divide the second factor? If so, do you see why that solves the problem?


    Too many laps on the same circuit: 2^{2n-1}=2\!\!\pmod 3\,\,\,\forall n\in\mathbb{N}

    Tonio
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Banned
    Joined
    Nov 2010
    Posts
    58
    Thanks
    18
    Quote Originally Posted by tonio View Post
    Too many laps on the same circuit: 2^{2n-1}=2\!\!\pmod 3\,\,\,\forall n\in\mathbb{N}

    Tonio
    I'm glad to see that you know how to solve the problem, but I was trying to help the OP figure this out on his own.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Newbie
    Joined
    Dec 2010
    Posts
    10
    Oh, I see!! Thanks both of you
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: January 10th 2011, 09:51 AM
  2. Euler path and Euler circuit problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 19th 2010, 09:18 PM
  3. Euler's Theorem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 5th 2009, 10:07 AM
  4. Euler's Theorem
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: May 5th 2008, 05:19 PM
  5. Euler's theorem
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: February 25th 2007, 01:53 PM

Search Tags


/mathhelpforum @mathhelpforum