# Thread:

1. ## Is there a quicker way to solve this congruence

Is $2^{35} \equiv 1 \textrm{ mod } 561$?

In the question we were given maple commands to use so I assume we were meant to do it that way. Is there a way to solve this without a calculator?

I had to use one but just did it like...

$2^8 = 256$,
so $2^{16} = 450$ mod 561
and $2^{32} = (2^{16})^2 = 103$ mod 561...

Then $2^{35} = 2^{32} 2^3 = 103 \times 8$ which is not equal to 1 mod 561..

2. Originally Posted by Deadstar
Is $2^{35} \equiv 1 \textrm{ mod } 561$?

Since $561=3\cdot 11\cdot 17$ , we can do:

*** Arithmetic modulo $3$ : $2^{35}=(2^3)^{11}\cdot 2^2=2^{11}\cdot 2^2=(2^3)^4\cdot 2=2^4\cdot 2=2^3\cdot 2^2=2^3=2\!\!\!\pmod 3$

*** Arithmetic modulo $11$ : $2^{35}=(2^{11})^3\cdot 2^2=2^3\cdot 2^2=32=10=-1\!\!\!\pmod {11}$

*** Arithmetic modulo $17$ : $2^{35}=(2^{17})^2\cdot 2=2^2\cdot 2=8\!\!\!\pmod {17}$ .

Well, now use the Chinese Remainder Theorem to find an element $x\in\mathbb{Z}\,\,\,s.t.\,\,\,x=2\!\!\!\pmod 3\,,\,x=-1\!\!\!\pmod {11}\,,\,x=8\!\!\!\pmod{17}$ .

I found $x=-298=263\!\!\!\pmod{561}\Longrightarrow 2^{35}=263\!\!\!\pmod{561}$ , as you can easily check with any calculator.

Tonio

In the question we were given maple commands to use so I assume we were meant to do it that way. Is there a way to solve this without a calculator?

I had to use one but just did it like...

$2^8 = 256$,
so $2^{16} = 450$ mod 561
and $2^{32} = (2^{16})^2 = 103$ mod 561...

Then $2^{35} = 2^{32} 2^3 = 103 \times 8$ which is not equal to 1 mod 561..
.
{"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": 19, "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": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9583747982978821, "perplexity_flag": "head"}