Results 1 to 5 of 5

Math Help - Help Understanding Modular Exponentiation

  1. #1
    Member
    Joined
    Jan 2011
    Posts
    156

    Help Understanding Modular Exponentiation

    I've come across an example that I can't understand. Can somebody explain what is happening here?

    2^{2^{1234}} \mod 3

    So, I get that if I can get the base to be something that is equal to 1 (mod 3), then I know that the overall answer is also 1 mod 3. What I don't understand is the simplification that is used.

    The example just shows one more step before jumping to the final answer. Here is what it shows:

    2^{2^{1234}} \equiv (2 \times 2) ^ {2 ^ {1233}} \equiv 1 \mod 3

    I can see that they got the base to be 4, which is 1 (mod 3), but I just can't follow the math for how they were able to make this leap. Can anybody tell me the exponentiation rule used?

    Thank you!
    Last edited by joatmon; September 30th 2012 at 09:51 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,619
    Thanks
    592

    Re: Help Understanding Modular Exponentiation

    Hey joatmon.

    I'm not sure given only this amount of information, but one thing that may help is to note that if a is congruent 1 MOD 3 then a^2 is also congruent to 1 MOD 3.

    So a = 3b + 1 for some b. This means

    a^2 = (3b+1)^2 = (3b)^2 + 6b + 1 = 3*(3b^2 + 2b) + 1 = 3c + 1 so a^2 is congruent to 1 MOD 3.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jan 2011
    Posts
    156

    Re: Help Understanding Modular Exponentiation

    Thanks for the reply, Chiro. That might be part of it. The usual procedure is that we try to get the base down to something that is 1 mod N, because we know that repeated multiplication of anything that is 1 mod N will always remain congruent to 1 since 1 x 1 x 1 x ... is still 1. I'm pretty sure that they somehow extracted a 2^1 from the exponent, but I don't see how they can bring this into the base.

    My guess is that they did something like this for the next two steps (which weren't shown):

    2^{2^{1234}} \equiv 2^{2^{1 + 1233}} \equiv 2^{2^12^{1233}}

    And then somehow brought down 4 into the base, but I don't see how this can be legally done. I'm sure that there is some exponential rule being applied that I am just not seeing, but this is as far as I can get.
    Last edited by joatmon; October 1st 2012 at 07:33 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,569
    Thanks
    1409

    Re: Help Understanding Modular Exponentiation

    The simplest way to do this is to note that "1234" is larger than 3 so start by reducing that "modulo 3".
    1234= what (mod 3)?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,710
    Thanks
    629

    Re: Help Understanding Modular Exponentiation

    Hello, joatmon!

    You're on the right track . . . keep going!


    My guess is that they did something like this for the next two steps (which weren't shown):

    2^{2^{1234}} \;=\; 2^{2^{1 + 1233}} \:=\: 2^{2^12^{1233}} . Good!

    You have: . 2^{2\cdot2^{1233}} \;=\;\left(2^2\right)^{2^{1233}} \;=\;(4)^{2^{1233}}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. modular exponentiation example
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 3rd 2012, 12:03 PM
  2. Modular Exponentiation
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 13th 2010, 01:54 PM
  3. Modular Exponentiation
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 13th 2010, 05:31 PM
  4. Modular exponentiation
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: March 8th 2009, 11:08 PM
  5. Modular Exponentiation
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 27th 2008, 04:31 PM

Search Tags


/mathhelpforum @mathhelpforum