Find the remainder when 2 1 9 9 0 is divided by 1990.
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.
That was really a quick and good way to solove :)
Nice solution. It can also be done by C.R.T.
Log in to reply
Can you show us your solution?
Log in to reply
Sure sir, its here.
Since, we have to calculate the remainder of 1 9 9 0 2 1 9 9 0 , it is equivalent to calculate the remainder of 9 9 5 2 1 9 8 9 .
Now observe that 9 9 5 = 1 9 9 × 5 .
First let us calculate 2 1 9 8 9 ( m o d 5 ) .
As 2 4 ≡ 1 ( m o d 5 ) , 2 1 9 8 9 ≡ 2 ( m o d 5 ) .
Again , observe that 2 1 9 8 ≡ 1 ( m o d 1 9 9 ) ,
So, 2 1 9 8 9 ≡ 1 1 4 ( m o d 1 9 9 ) .
Now apply C.R.T to get
1 9 9 x + 1 1 4 = 5 k + 2 for some x and k .
Interospecting we get 5 1 2 as a least common value of these equations.
Now, as we eliminated 2 in the beginning , we multiply 5 1 2 with 2 to get 1 0 2 4 , the desired answer.
Log in to reply
@Priyanshu Mishra – Yes, that works too (+1)...thanks!
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.
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 1 5 ) since ϕ ( 1 5 ) = ϕ ( 3 ) ∗ ϕ ( 5 ) = 2 ∗ 4 = 8 but Carmichael tells us that a 4 ≡ 1 ( m o d 1 5 ) since λ ( 1 5 ) = l c m ( 2 , 4 ) = 4 , where a is coprime to 15.
@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!
@Priyanshu Mishra – Why dont you place it as a solution?
Log in to reply
@Satyajit Ghosh – Oh, sorry. Sir Otto asked me for another solution, so i replied him.
Since we need to find out what 2 1 9 9 0 m o d 1 9 9 0 is, then we can just look for 2 1 9 9 0 m o d 2 , 5 , a n d 1 9 9 The smallest possible k is 5. Therefore, x= (199)(5) +29 = 1024 .
Problem Loading...
Note Loading...
Set Loading...
Since the Carmichael lambda of 995 is 396, we have 2 1 9 9 0 = 2 5 ∗ 3 9 6 + 1 0 ≡ 2 1 0 ( m o d 9 9 5 ) and 2 1 9 9 0 ≡ 2 1 0 = 1 0 2 4 ( m o d 1 9 9 0 )