Results 1 to 4 of 4

Thread: a^n in mod

  1. #1
    Junior Member
    Joined
    Apr 2010
    Posts
    59

    a^n in mod

    Hey

    It's been a while since I posted here, but here goes:

    I have to (in basic terms) work out what:
    $\displaystyle 72^{5712} mod 101$ is,

    I've started by applying Euler's theorem and moved it down to:

    $\displaystyle 72^{100x57 +12}$

    but I'm stuck, as I'm not sure how this is going to give me a final result.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78
    Quote Originally Posted by ramdrop View Post
    Hey

    It's been a while since I posted here, but here goes:

    I have to (in basic terms) work out what:
    $\displaystyle 72^{5712} mod 101$ is,

    I've started by applying Euler's theorem and moved it down to:

    $\displaystyle 72^{100x57 +12}$

    but I'm stuck, as I'm not sure how this is going to give me a final result.
    You have a good start by Fermat's little theorem we get that

    $\displaystyle 72^{100} \equiv 1 \text{mod}(101) $

    This gives

    $\displaystyle (72^{100})^{57}72^{12} \text{mod}(101)\equiv 72^{12} \text{mod}(101) \equiv 3^{24}\cdot 2^{36} \text{mod}(101)$

    Now further note that

    $\displaystyle 2^9 \text{mod}(101)\equiv 7 \text{mod}(101)$ and

    $\displaystyle 3^6 \text{mod}(101)\equiv 22 \text{mod}(101)$

    Using this we get

    $\displaystyle 3^{24}\cdot 2^{36} \text{mod}(101)\equiv 22^4\cdot7^4 \text{mod}(101)\equiv (154)^4 \text{mod}(101)\equiv (53)^4 \text{mod}(101)$

    Now just multiply it out and divide by 101 to find the remainder

    I end up with $\displaystyle 58$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Apr 2010
    Posts
    59
    An interesting approach, thanks a lot

    I'm still trying to approach it by Euler's, but at least I have some idea what the end result will be.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78
    Quote Originally Posted by ramdrop View Post
    An interesting approach, thanks a lot

    I'm still trying to approach it by Euler's but at least I have some idea what the end result will be.
    Just FYI Euler's theorem is a generalization of Fermat's little theorem.

    Since Sine $\displaystyle P=101$ is prime $\displaystyle 72$ and 101 are coprime and Euler's theorem reduces to Fermat's little theorem. The proof should be identical!
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum