# Thread:

1. ## 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?

2. 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)$

3. 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

4. Ok! Now I am understand what you tried to do!

You thought using Fermat's little theorem.

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...

5. Originally Posted by Also sprach Zarathustra
Ok! Now I am understand what you tried to do!

You thought using Fermat's little theorem.

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.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 16, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9292500615119934, "perplexity_flag": "middle"}