Results 1 to 3 of 3

Thread: 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 $\displaystyle a, n \in Z$ and $\displaystyle gcd(a,n)=1$ and Euler's phi-function,

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

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

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

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

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

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

    so... $\displaystyle 27^{40}\ mod\ 100 = 1\ mod\ 100$
    then $\displaystyle 27^{80}\ mod\ 100 = 1\ mod\ 100$
    but we still have a $\displaystyle 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
    $\displaystyle \phi(100)=40$ So we have $\displaystyle 3^{40}\equiv 1 (\bmod.100)$

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

    Now what can you say about $\displaystyle 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; Nov 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 $\displaystyle a, n \in Z$ and $\displaystyle gcd(a,n)=1$ and Euler's phi-function,

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

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

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

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

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

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

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

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

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

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

    Now we calculate modulo 100. Euler's Theorem implies that $\displaystyle 3^{40}\equiv1\pmod{100}$; thus $\displaystyle 3^{3^{100}}=3^{1+40k}=3\cdot(3^{40})^k\equiv3\cdot 1^k\equiv3\pmod{100}$.
    Last edited by melese; Nov 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: Mar 3rd 2012, 12:03 PM
  2. Modular Exponentiation Calculator
    Posted in the Math Software Forum
    Replies: 6
    Last Post: Apr 2nd 2011, 07:25 AM
  3. Modular Exponentiation
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Sep 13th 2010, 05:31 PM
  4. Modular exponentiation
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: Mar 8th 2009, 11:08 PM
  5. Modular Exponentiation
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Aug 27th 2008, 04:31 PM

Search Tags


/mathhelpforum @mathhelpforum