Results 1 to 3 of 3

Math Help - Modular Exponentiation

  1. #1
    Member
    Joined
    Oct 2009
    Posts
    128

    Modular Exponentiation

    Hello!

    I am trying to apply a result from a theorem to an example.

    There is a thorem that states, for a, n \in Z and gcd(a,n)=1 and Euler's phi-function,

    a^{\phi(n)}\ mod\ n = 1\ mod\ n

    So I am trying to determine the last two digits of 3^{3^{100}}

    So, Essentially, 3^{3^{100}}\ mod\ 100 = ?

    Well, 3^{3^{100}} = 27^{100} I believe.

    Then, since
    gcd(27, 100) = 1,
    we have 27^{\phi(100)}\ mod\ 100= 1\ mod\ 100

    Well, \phi(100) = \phi(5^2)\phi(2^2) = (5^2 - 5)(2^2 - 2) = (20)(2) = 40

    so... 27^{40}\ mod\ 100 = 1\ mod\ 100
    then 27^{80}\ mod\ 100 = 1\ mod\ 100
    but we still have a 27^{20}\ mod\ 100 left to deal with. That is where I'm stuck.

    Anybody have any ideas? Thanks!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    \phi(100)=40 So we have 3^{40}\equiv 1 (\bmod.100)

    Now note that if a\equiv b (\bmod.40) then a = b + 40\cdot k and so 3^{a} = 3^b\cdot \left(3^{40}\right)^k \equiv 3^b\cdot 1^k \equiv 3^b (\bmod.100) so to find 3^{3^{100}}(\bmod.100) we may instead find 3^{100} (\bmod.40) and raise 3 to that -module 100.

    Now what can you say about 3^{100} (\bmod.40) ? ... 3⁴ = ?

    Note that if you didn't spot the thing about 3⁴ you could still repeat the procedure above for 3⁰⁰ mod 40
    Last edited by PaulRS; November 13th 2010 at 02:19 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Quote Originally Posted by matt.qmar View Post
    Hello!

    I am trying to apply a result from a theorem to an example.

    There is a thorem that states, for a, n \in Z and gcd(a,n)=1 and Euler's phi-function,

    a^{\phi(n)}\ mod\ n = 1\ mod\ n

    So I am trying to determine the last two digits of 3^{3^{100}}

    So, Essentially, 3^{3^{100}}\ mod\ 100 = ?

    Well, 3^{3^{100}} = 27^{100} I believe.

    Then, since
    gcd(27, 100) = 1,
    we have 27^{\phi(100)}\ mod\ 100= 1\ mod\ 100

    Well, \phi(100) = \phi(5^2)\phi(2^2) = (5^2 - 5)(2^2 - 2) = (20)(2) = 40

    so... 27^{40}\ mod\ 100 = 1\ mod\ 100
    then 27^{80}\ mod\ 100 = 1\ mod\ 100
    but we still have a 27^{20}\ mod\ 100 left to deal with. That is where I'm stuck.

    Anybody have any ideas? Thanks!!
    Euler's Theorem. Let n be a positive integer. Then a^{\phi(n)}\equiv1\pmod n, if \displaystyle gcd(a,n)=1.

    First 3^{3^{100}} actually means 3^{(3^{100})}, not (3^3)^{100}!

    Since \phi(100)=40 we want to find the remainder of 3^{100} when divided by 40. Begin with the observation that 3^4=81\equiv1\pmod{40}, so 3^{100}=(3^4)^{25}\equiv1\pmod{40}. Therefore 3^{100}=1+40\cdot k for some positve integer k.

    Now we calculate modulo 100. Euler's Theorem implies that 3^{40}\equiv1\pmod{100}; thus 3^{3^{100}}=3^{1+40k}=3\cdot(3^{40})^k\equiv3\cdot  1^k\equiv3\pmod{100}.
    Last edited by melese; November 13th 2010 at 03:30 PM.
    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 Calculator
    Posted in the Math Software Forum
    Replies: 6
    Last Post: April 2nd 2011, 07:25 AM
  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