Fun with modulo #1

Find the remainder when 2 1990 { 2 }^{ 1990 } is divided by 1990.


The answer is 1024.

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.

2 solutions

Otto Bretscher
Oct 17, 2015

Since the Carmichael lambda of 995 is 396, we have 2 1990 = 2 5 396 + 10 2 10 ( m o d 995 ) 2^{1990}=2^{5*396+10}\equiv 2^{10} \pmod{995} and 2 1990 2 10 = 1024 ( m o d 1990 ) 2^{1990}\equiv 2^{10}=\boxed{1024} \pmod{1990}

That was really a quick and good way to solove :)

Satyajit Ghosh - 5 years, 8 months ago

Nice solution. It can also be done by C.R.T.

Priyanshu Mishra - 5 years, 7 months ago

Log in to reply

Can you show us your solution?

Otto Bretscher - 5 years, 7 months ago

Log in to reply

Sure sir, its here.

Since, we have to calculate the remainder of 2 1990 1990 \large\ \frac { { 2 }^{ 1990 } }{ 1990 } , it is equivalent to calculate the remainder of 2 1989 995 \large \frac { { 2 }^{ 1989 } }{ 995 } .

Now observe that 995 = 199 × 5 995=199 \times 5 .

First let us calculate 2 1989 ( m o d 5 ) \large\ { 2 }^{ 1989 }\pmod{ 5 } .

As 2 4 1 ( m o d 5 ) { 2 }^{ 4 }\equiv1 \pmod{5} , 2 1989 2 ( m o d 5 ) { 2 }^{ 1989 }\equiv2 \pmod{5} .

Again , observe that 2 198 1 ( m o d 199 ) { 2 }^{ 198 }\equiv1 \pmod{199} ,

So, 2 1989 114 ( m o d 199 ) { 2 }^{ 1989 }\equiv114 \pmod{199} .

Now apply C.R.T to get

199 x + 114 = 5 k + 2 199x + 114 = 5k + 2 for some x x and k k .

Interospecting we get 512 512 as a least common value of these equations.

Now, as we eliminated 2 2 in the beginning , we multiply 512 512 with 2 2 to get 1024 \boxed{1024} , the desired answer.

Priyanshu Mishra - 5 years, 7 months ago

Log in to reply

@Priyanshu Mishra Yes, that works too (+1)...thanks!

Otto Bretscher - 5 years, 7 months ago

Log in to reply

@Otto Bretscher Sir, one more thing i want to ask you that what is the use of Carmichael numbers and lambda in solving congruence ? I have seen in some solutions by you, that you used Carmichael lambda and the answer came in just one line.

So, please help me so that i can apply this theory to other problems also.

Priyanshu Mishra - 5 years, 7 months ago

Log in to reply

@Priyanshu Mishra There is a good description here . The basic idea is simple: Use LCM instead of Euler's product. Consider the case of 15 where Euler tells us that a 8 1 ( m o d 15 ) a^8 \equiv 1 \pmod{15} since ϕ ( 15 ) = ϕ ( 3 ) ϕ ( 5 ) = 2 4 = 8 \phi(15)=\phi(3)*\phi(5)=2*4=8 but Carmichael tells us that a 4 1 ( m o d 15 ) a^4 \equiv {1} \pmod{15} since λ ( 15 ) = l c m ( 2 , 4 ) = 4 \lambda(15)=lcm(2,4)=4 , where a a is coprime to 15.

Otto Bretscher - 5 years, 7 months ago

@Otto Bretscher Sir even I am not able to find a wiki on Carmichael Lambda. It will be really useful if you can create a wiki on this!

Satyajit Ghosh - 5 years, 7 months ago

@Priyanshu Mishra Why dont you place it as a solution?

Satyajit Ghosh - 5 years, 7 months ago

Log in to reply

@Satyajit Ghosh Oh, sorry. Sir Otto asked me for another solution, so i replied him.

Priyanshu Mishra - 5 years, 7 months ago
Madelyn Yu
Jun 1, 2016

Since we need to find out what 2 1990 m o d 1990 2^{1990}\mod 1990 is, then we can just look for 2 1990 m o d 2 , 5 , a n d 199 2^{1990}\mod 2,5, and\ 199 The smallest possible k is 5. Therefore, x= (199)(5) +29 = 1024 .

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...