How do you determine the remainder when a very large number is divided by a large divisor, such as:
10^1,000 mod 348,989=?. I mean, I pretty well know the rules of dividing by small integers of 2 - 9, but dividing by a large number such as the given example is a mystery to me. Anybody with insights or references would be appreciated. I thank you for any help.
Thanks Melody. I do realize that you can get the answer by using a good calculator, such as Web2.0, HP scientific calculator, Wolfram/Alpha.....etc. What I was wondering about is this: Is there a manual rule or method that one can use to determine the remainder without resorting to sophisticated calculators?. These calculators must surly use some algorithm to arrive at the answer so quickly. They, almost certainly, do not use long division to determine the remainder.
+118658 Yes I thought that might be the case. :)
I did look at breaking up 348989 into its prime factors but it is a prime number already so that didn't help.
I am relatively new at modular arithemtic too. I don't think I had ever done any of it before they started appearing on this site. So no I don't have any great ideas either.
