Results 1 to 4 of 4

Thread: 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 $\displaystyle gcd(a, m) = 1$, $\displaystyle a^{\varphi{(m)}} \equiv 1 \pmod{m}$, where $\displaystyle \varphi{(m)}$ is the Euler totient of $\displaystyle m$.

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

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

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

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

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

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

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

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

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

    And we are done ! We can now write :

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

    $\displaystyle \therefore 71^{71} \equiv 11 \pmod{17}$ (that is, $\displaystyle 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
    22
    Quote Originally Posted by meshel88 View Post
    71^71 is congruent to x(mod 17)
    $\displaystyle 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