Results 1 to 4 of 4

Math Help - another mod

  1. #1
    Newbie
    Joined
    Feb 2010
    Posts
    21

    another mod

    71^71 is congruent to x(mod 17)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Hello,
    use Euler's generalization of Fermat's Little Theorem : if and only if gcd(a, m) = 1, a^{\varphi{(m)}} \equiv 1 \pmod{m}, where \varphi{(m)} is the Euler totient of m.

    In your case, 17 is a prime number (lucky you), so \varphi{(17)} = 17 - 1 = 16. And gcd(71, 17) = 1. Therefore, 71^{16} \equiv 1 \pmod{17}. Good.

    Now note that 71^{71} \equiv (71^{16})^4 \times 71^7 \pmod{17}. Plug in the result you found with Euler's generalization, you find that :

    71^{71} \equiv 1^4 \times 71^7 \equiv 71^7 \pmod{17}.

    71^7 still is a big number, so we are going to break it into pieces. You can thus write the following :

    71^{71} \equiv 71^7 \equiv (71^2)^3 \times 71^1 \pmod{17}.

    You can easily compute 71^2 \equiv 5041 \equiv 9 \pmod{17}, so :

    (71^2)^3 \times 71 \equiv 9^3 \times 71 \pmod{17}

    9^3 is not too big and can be computed quickly (if not, break it into two pieces), so 9^3 \equiv 729 \equiv 15 \pmod{17}. While we're at it, 71 \equiv 3 \pmod{17}. We get :

    9^3 \times 71 \equiv 15 \times 3 \equiv 45 \equiv 11 \pmod{17}.

    And we are done ! We can now write :

    71^{71} \equiv 71^7 \equiv (71^2)^3 \times 71^1 \equiv 11 \pmod{17}.

    \therefore 71^{71} \equiv 11 \pmod{17} (that is, x = 11)

    --------

    Can you see how I have repeatedly broken the original, gigantic number, into lots of smaller numbers, using Fermat's Generalized Little Theorem as a starting block and using algebra of indices to finish off the work ?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by meshel88 View Post
    71^71 is congruent to x(mod 17)
    71^71\equiv 3^{71}\equiv 3^{7}. Continue
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Oh, how could I miss that, of course you should simplify the base first
    My bad ...
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum