congruence....

Number Theory Level 2

What will be the remainder if (2^44)-1 is divided by 89 ?


The answer is 0.

Trishit Chandra by Trishit Chandra , 23, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Omkar Kulkarni
Dec 29, 2014

2 44 − 1 = ( 2 11 − 1 ) ( 2 11 + 1 ) ( 2 22 + 1 ) 2^{44}-1=(2^{11}-1)(2^{11}+1)(2^{22}+1)

2 11 − 1 2^{11}-1 happens to be a multiple of 89. That's all I can think of.

2 Helpful 0 Interesting 0 Brilliant 0 Confused

I've also done the problem in this manner. :D

Trishit Chandra - 6 years, 5 months ago

By Euler's Criterion ( 2 / 89 ) ≡ 2 44 ( m o d ⁣ 89 ) (2/89)\equiv 2^{44}\pmod{\! 89} , which is 1 1 , since by Quadratic Reciprocity 89 ≡ ± 1 ( m o d ⁣ 8 ) ⇒ ( 2 / 89 ) = 1 89\equiv \pm 1\pmod{\!8}\,\Rightarrow\, (2/89)=1 .

mathh mathh - 6 years ago

Log in to reply

Ahh yes. Thanks! :D

Omkar Kulkarni - 6 years ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...