Results 1 to 5 of 5

Math Help - Modular arithmetic

  1. #1
    Banned
    Joined
    Mar 2011
    Posts
    118

    Modular arithmetic

    If 2 numbers a=b mod(n), does that imply they are congruent modulo as well?

    Anyway on to the matter at hand. Calculate 2^258 (mod 259)I did it 2 different ways and unfortunatly got 2 different answers.

    2^(64)=86 mod 259,
    2^(128)=144,
    2^(256)=16 so 2^256.2^2=64 (mod 259). I know my method isn't very clear but you probably get the idea.

    Method 2

    259 = 7 x 37

    2^6=1 mod(7)

    2^258=(2^6)^43=1 mod (7)

    2^36=1 mod(37)

    2^258=(2^36)^7.2^6=27 mod(37)

    but 1 x 27=27 not 64.
    I have a strong feeling my first method is correct. Which one is correct and why is the other wrong?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    The first is the correct one. Unfortunately, I don't understand your second method.

    My way:

    (2^8)^{32}\cdot 2^3=2^{258}

    2^8(mod259)\equiv -2

    2^{258}=(2^8)^{32}\cdot 2^3\equiv(-2)^{32}\cdot 2^3=2^{34}=(2^8)^4\cdot 2^2\equiv (-2)^4\cdot 2^2=2^6=64(mod259)
    Last edited by Also sprach Zarathustra; March 18th 2011 at 03:14 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Mar 2011
    Posts
    118
    Quote Originally Posted by Also sprach Zarathustra View Post
    The first is the correct one. Unfortunately, I don't understand your second method.

    My way:

    (2^8)^32\cdot 2^3=2^258

    2^8(mod259)\equiv -2

    2^258=(2^8)^32\cdot 2^3\equiv(-2)^32\cdot 2^3=2^34=(2^8)^4\cdot 2^2\equiv (-2)^4\cdot 2^2=2^6=64(mod259)
    Explaining my second answer. I've seen it that you can express the modulus as a factor of primes and then find your a^b under each modulus you should get the same answer both times,(Your not meant to multiply them as i did). Here is a link with an example using this method.

    http://uk.answers.yahoo.com/question...3030517AA4R5UI
    Last edited by poirot; March 17th 2011 at 03:39 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    Ok! Now I am understand what you tried to do!

    You thought using Fermat's little theorem.

    This theorem is not so helpful in your case. Why?

    There is a lemma which states:

    If p and q are different primes and a^p\equiv a(mod q) and a^q\equiv a(mod p), then a^{pq}\equiv a(modpq)

    Try to work with that in your question, and see what you get...
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Mar 2011
    Posts
    118
    Quote Originally Posted by Also sprach Zarathustra View Post
    Ok! Now I am understand what you tried to do!

    You thought using Fermat's little theorem.

    This theorem is not so helpful in your case. Why?

    There is a lemma which states:

    If p and q are different primes and a^p\equiv a(mod q) and a^q\equiv a(mod p), then a^{pq}\equiv a(modpq)

    Try to work with that in your question, and see what you get...
    The only thing I don't understand is that the answer they obtained was 4, not 2 as the lemma demands.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 4th 2011, 12:07 AM
  2. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 3rd 2011, 02:37 PM
  3. Modular Arithmetic
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 28th 2010, 06:08 AM
  4. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 13th 2008, 04:17 PM
  5. modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 25th 2007, 09:39 PM

Search Tags


/mathhelpforum @mathhelpforum