RMO 2015! #3
Find the remainder when 2 1 9 9 0 is divided by 1 9 9 0
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
pleasedo explain fermats little theorm to me with proof.please sir
Log in to reply
Fermat's little theorem states that a p − 1 ≡ 1 ( m o d p ) when p is a prime that does not divide a .
There are several short and easy proofs. The congruency classes of a , 2 a , 3 a , . . . ( p − 1 ) a are those of 1 , 2 , 3 , . . . , p − 1 , so, taking the product in each case, we see that a p − 1 ( p − 1 ) ! ≡ ( p − 1 ) ! ( m o d p ) . Division by ( p − 1 ) ! gives our theorem.
Log in to reply
could not understand the proof .but thanks for explaining it
Log in to reply
@Kaustubh Miglani – The key point of the proof is this: If m and n are any two distinct integers between 1 and p − 1 , then the prime number p does not divide m a − n a = ( m − n ) a since p divides neither m − n nor a . Thus the numbers a , 2 a , . . . , ( p − 1 ) a occupy all the congruency classes 1 , . . . , p − 1 ( m o d p ) .
please do explain fermats little theorm to me with proof.please sir
is it necessary that if x is divided bya b c and leaves the same remainder when divided by a,b and c then the remainder would be same if x is divided by abc
Hi sir, please explain 2^1990 mod 2 = 2^10. Is it 2^1990 mod 2 equal to zero?
Log in to reply
I'm just expressing the trivial fact that 2 1 9 9 0 − 2 1 0 is divisible by 2.
Or we can apply chinese remainder theorm after reducing 1990 to 995 and breaking 995 to 5 and 199. Then solving individually using Euler's Totient function, and multipling the remainder by 2 ( since we earlier cancelled 2) we will get 1024.
Hello Pranjal,
How was your RMO 2015? What score you expect?
Using Fermat's little theorem for p = 1 9 9 and for p = 5 , we find that 2 1 9 9 0 = 2 1 9 8 ∗ 1 0 + 1 0 ≡ 2 1 0 ( m o d 1 9 9 ) and 2 1 9 9 0 = 2 4 ∗ 4 9 5 + 1 0 ≡ 2 1 0 ( m o d 5 ) . Trivially, 2 1 9 9 0 ≡ 2 1 0 ( m o d 2 ) . Thus 2 1 9 9 0 ≡ 2 1 0 = 1 0 2 4 ( m o d 1 9 9 0 ) .