Results 1 to 7 of 7

Math Help - Modular arithmetic without a calculator

  1. #1
    Member
    Joined
    Jul 2011
    Posts
    196

    Modular arithmetic without a calculator

    I think I am not understanding something properly as I keep having problems with modular arithmetic for some reason. For example, I am given this:

    Compute: 3^{20} mod 71

    So I understand that there is a number x that is = 3^{20} less a multiple of 71. So with my calculator I do the following:

    \frac{3^{20}}{71} = 49109639.4507042254

    0.4507042254\times 71 = 32

    \therefore the original statement is congruent with 32 mod 71

    Or I just find how many whole times 71 will go into 3^{20}. multiply 71 by that number and then subtract it form 3^{20} to be left with 32.

    I can't seem to understand my notes on how to do it without a calculator and now I have a problem doing the following (my calculator just shows error):

    5^{4675} mod 89

    Can someone walk me through what they are thinking/trying to do when breaking these down without a calculator? or direct me to a resource that does a better job of explaining this - I can't seem to grasp it yet.

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Re: Modular arithmetic without a calculator

    Quote Originally Posted by terrorsquid View Post
    I think I am not understanding something properly as I keep having problems with modular arithmetic for some reason. For example, I am given this:

    Compute: 3^{20} mod 71

    So I understand that there is a number x that is = 3^{20} less a multiple of 71. So with my calculator I do the following:

    \frac{3^{20}}{71} = 49109639.4507042254

    0.4507042254\times 71 = 32

    \therefore the original statement is congruent with 32 mod 71

    Or I just find how many whole times 71 will go into 3^{20}. multiply 71 by that number and then subtract it form 3^{20} to be left with 32.

    I can't seem to understand my notes on how to do it without a calculator and now I have a problem doing the following (my calculator just shows error):

    5^{4675} mod 89

    Can someone walk me through what they are thinking/trying to do when breaking these down without a calculator? or direct me to a resource that does a better job of explaining this - I can't seem to grasp it yet.

    Thanks.
    By Euler's theorem,

    5^{88}\equiv 1\pmod{89}

    (5^{88})^{53}\equiv 1\pmod{89}

    5^{4664}\equiv 1\pmod{89}

    5^{4675}\equiv 5^{11}\pmod{89}

    Now proceed as you did in the case of 3^{20} mod 71.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jul 2011
    Posts
    196

    Re: Modular arithmetic without a calculator

    I don't understand why you split 4675 into 88x53 + 11.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4

    Re: Modular arithmetic without a calculator

    Quote Originally Posted by terrorsquid View Post
    I don't understand why you split 4675 into 88x53 + 11.
    Because:

    (5^{88})^{53} \times 5^{11} = 5^{4675}

    which we do because we know that 5^{88} \equiv 1 \text{ mod } 89 so we know that (5^{88})^{53} \equiv 1 \text{ mod } 89 which leaves us with:

    5^{4675} \equiv 5^{11}  \text{ mod } 89

    which is relatively easy to finish off.

    CB
    Last edited by CaptainBlack; October 8th 2011 at 12:24 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jul 2011
    Posts
    196

    Re: Modular arithmetic without a calculator

    So, you determined that 89 was prime, therefore 5^{89-1} \equiv 1 mod 89... then found how many times 88 went into 4675 as a whole, leaving 5^{11} which you can calculate easily. I think I understand the method, what do I search for in google if I wanted to learn the reasoning behind all this? Just "Euler's Theorem"?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4

    Re: Modular arithmetic without a calculator

    Quote Originally Posted by terrorsquid View Post
    I think I understand the method, what do I search for in google if I wanted to learn the reasoning behind all this? Just "Euler's Theorem"?
    No, try "Fermat's Little Theorem". While "Euler's Theorem" may be technically correct since he was the first to publish a proof, Euler is responsible for so many results you will be swamped with other stuff if you search for "Euler's Theorem".

    CB
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: Modular arithmetic without a calculator

    the number of positive integers from 1 to n-1 (inclusive) of numbers co-prime to n, has a special name, φ(n), or "totient of n".

    euler's theorem states that if (k,n) = 1, that k^φ(n) = 1 (mod n).

    for example, φ(6) = 2, because only 1 and 5 are co-prime to 6.

    this means that we know (without calculating at all), that 25 = 1 (mod 6) (easy enough to check in your head).

    if we have a prime p, then φ(p) = p-1, so for all 1 ≤ k < p, k^(p-1) = 1 (mod p).

    so, for example, 7^12 = 1 (mod 13).

    as a practical matter, let's look at your original example, 3^20 (mod 71).

    i promise not to use my calculator for this....

    71 is prime (hopefully you can see this at once). let's see if we can't take some lesser power, first.

    3^20 = (3^4)^5. 3^4 is 81, and 81 is 10 (mod 71)

    so 3^20 = 10^5 (mod 71). isn't that looking better?

    10^5 = (100)(100)10, and 100 = 29 (mod 71).

    so 10^5 = (29)(29)(10) (mod 71).

    290 = 6 (mod 71) so 10^5 = (29)(6) (mod 71). looking pretty good, now.

    (29)(6) = 174 = 32 (mod 71). there! all done
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. modular arithmetic help
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 9th 2011, 06:50 AM
  2. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 4th 2011, 12:07 AM
  3. Modular Exponentiation Calculator
    Posted in the Math Software Forum
    Replies: 6
    Last Post: April 2nd 2011, 08:25 AM
  4. Some modular arithmetic
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 25th 2010, 12:41 PM
  5. Modular Arithmetic
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 28th 2010, 06:08 AM

Search Tags


/mathhelpforum @mathhelpforum