Rush down then up!
Given that { A = 9 9 9 , 9 9 3 ! B = 1 , 0 0 0 , 0 0 3 Find the remainder when A is divided by B .
Note: B is a prime number.
The answer is 49088.
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
I don't understand. Where did you get 362880 from?
Log in to reply
We need A mod(B)...............Suppose that A = x mod(B)..............Now, we get 1 = 362880x mod(B)............!!!! (Because, by Wilson's Theorem, (B-2)! = 1 mod(B)..........SO, we need to multiply and divide A by all the numbers from 999,994 to 1,000,001.........Then, seeing that all those numbers are congruent to -9,-8,-7.....-2 mod(B), respectively, we get the expression stated!!!)
Log in to reply
I think this is a crucial step. It would better to show this in your solution.
Plus, how did you evaluate the modular multiplicative inverse of 262880 mod B?
Log in to reply
@Pi Han Goh – Well, Sir, evaluating a multiplicative inverse is a fairly standard technique............Or, if we are stuck, Wolfram Alpha is always there!!!!
Log in to reply
@Aaghaz Mahajan – I don't see how your solution is helpful. Your solution basically hints at using a common technique, while also skipping out a crucial step: The application of Wilson's Theorem. Plus, your last comment suggests that we just have to summon WolframAlpha, which I'm pretty sure goes against the spirit of solving this problem.
If someone who failed to solve this problem were to look at your solution, would they actually understand it? Sorry for sounding crass, but your solution is not benefiting anyone.
Log in to reply
@Pi Han Goh – No Sir, I get it........my solution is not the best.........But I tried to make it helpful..........I have mentioned the use of Wilson's Theorem and have also provided a great resource for learning Evaluation of Modular multiplicative inverse........... @Naren Bhandari @Pi Han Goh Could you please go through the solution again??
Log in to reply
@Aaghaz Mahajan – The flow of your solution is hard to parse.
First, know that you have to apply Wilson's theorem first before you apply modular multiplicative inverse.
What you have done is "Oh, it's just a typical modular multiplicative inverse question. How did I get it? I did Wilson's too!"
Why don't you show the steps in proper order?
You can even motivate readers by showing a very general statement from Wilsons':
We start with Wilson's theorem: 1000002! == -1 mod 1000003
==> 1000002! == 1000002 mod 1000003
==> 1000001! == 1 mod 1000003
==> 999993! * 999994 * 999995 * ... * 1000001 == 1 mod 1000003
==> 999993! * (-9) * (-8) * ... * (-2) == 1 mod 1000003
==> 999993! * 9! == 1 mod 1000003
So the answer is the modular multiplicative inverse of 9! mod 1000003.
This becomes a standard exercise:
Let "x" denote the answer to this question, then
362880x == 1 mod 1000003
Using Extended Euclidean Algorithm, we can see that 49088 * 362880 - 1000003 * 17813 = 1. So the answer is 49088.
Also, please refrain from using "....." in your solution. That just looks messy and split your solution into paragraphs.
Notice that I didn't use L A T E X either. I know that you're weak in L A T E X , but that doesn't mean that it's impossible for you to learn. While I know that you know how to solve math relatively hard math problems, it takes another skill to be able to explain how you solve them (clearly). So don't feel weird if you are not skilled in this area yet. You'll get there eventually if you keep trying.
Your solution is missing the crucial part to calculate the multiplicative inverse. My title is a way to calculate it( a bit lengthy might be). Let us know and learn your approach.
Relevant wiki: Wilson's Theorem
We just need to find the Modular multiplicative inverse of 362880 mod B...............!!
Explanation :- We need A mod(B)...............Suppose that A = x mod(B)..............Now, we get 1 = 362880x mod(B)............!!!! (Because, by Wilson's Theorem, (B-2)! = 1 mod(B)..........SO, we need to multiply and divide A by all the numbers from 999,994 to 1,000,001.........Then, seeing that all those numbers are congruent to -9,-8,-7.....-2 mod(B), respectively, we get the expression stated!!!) To know the technique of finding multiplicative inverses, start reading This Book from page number 13 onwards........!!! I hope it helps :)