Modular arithmetic

Printable View

March 17th 2011, 12:37 PM
poirot

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?
March 17th 2011, 01:30 PM
Also sprach Zarathustra

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)$
March 17th 2011, 01:52 PM
poirot

Quote:

Originally Posted by Also sprach Zarathustra

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
March 18th 2011, 03:44 AM
Also sprach Zarathustra

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...
March 21st 2011, 03:40 AM
poirot

Quote:

Originally Posted by Also sprach Zarathustra

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.