Results 1 to 4 of 4

Math Help - 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:
    72^{5712} mod 101 is,

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

    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:
    72^{5712} mod 101 is,

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

    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

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

    This gives

    (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

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

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

    Using this we get

    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 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 P=101 is prime 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