Divisibility of big numbers Suppose we have a number $N$ with $x$ digits and we want to determine whether $N$ is divisible by a number $M$ with $y$ digits such that $x > y$.
How do I go about this? I tried to use the first $y$ digits of $N$ and divide them by $M$ but I'm not sure this is true for all $N$ and $M$. Is there a general rule of thumb for problems like this?
 A: You ask two or three questions:


*

*Suppose we have a number N with x digits ...


If x = 1 then it's easy enough, I suppose. 
If x > 1 googolplex then if someone could answer your question, if humanity from now on would develop machines specifically designed to solve this problem, then you'd not be alive to receive the answer. 
Pulling people off of the task of answering the problem to devote themselves to ensuring your offspring continued, so they could accept the answer on your behalf, would only increase the time it took to solve the problem; and give your offspring the answer to a single pair of numbers (assuming x was enormous, or that you wanted more than one pair of numbers solved for).


*How do I go about this?


In a comment to your question @Harry49 gives this link: 
https://en.wikipedia.org/wiki/Divisibility_rule - I have no problem with that answer, it is one correct method albeit not a quick method.


*Is there a general rule of thumb for problems like this?


Rule of thumb: 


*

*What if the question was: "How do I go about counting all the atoms in the universe?" (unlike your question, that question has a clearly defined bound and it's a single question with one number produced as the answer).

*What if the agreed upon answer was: "You make a huge jar and count how many atoms it is made of, then you take each atom in the universe and place it in the jar; counting each as you go.".

So back we go to the "divisability rules" given in #2, and your question: "How do I go about this?".
The "answer" is either "Follow the divisibility rule", or the answer is "You, or we, do not (go about doing that)".
Even if a huge shortcut could be developed there's a huge number of numbers and providing the answer to a very large number would take a very long time, a prohibitively long time.
If X was trivial you could probably just look at it and know, much as some people know a large multiplication table, you could know a large division table - knowing that doesn't answer you question any better than using divisibility rules (which is unhelpful) or deriving an enormous shortcut (which would take an enormous amount of time, as would writing out the answer if we knew it).
Your problem is unbounded and thus unsolvable, giving the answer for one large X would take forever as would developing the fastest shortcut.
It's somewhat like asking "How do I calculate the last digit of π?". We can give you the best algorithm and computer but the doing is another matter. If your current position could be saved and transferred to a faster computer, or a better algorithm, you'd still not have a answer anytime soon (or late). How would you do it?, you would not.
A: Easiest way is to divide M into N and check for remainder as propsed by Ross Millikan in the comments section. You can do it with long division, where you have I believe $O(log(N/M)) = O(x-y)$ multiplications, subtractions and divisions (which we can disregard, since the reulst from those division is always exactly one digit, thus we can assume it is constant operation. The same thing aplies to multiplication since we're multiplicating M by a single digit). Most difficult of these is actually the subtraction which will take $O(x)$. Total is bound by $O(x^2)$. Maybe better explanation of this part can be found on StackOverflow.
Since I assume you are interested in big x and y and you want to be a little faster, you can do the division with Newton's method, which transforms the problem of set of multiplications, for which you can use FFT getting a complexity of $O(x*log(x)*log(log(x)))$.
There are of course the special cases of M being the $n$-th power of 2 where you need to check divisibility of only the first $n$ digits of N or other divisibility rules as shown earlier here but for the general case you have to do the division somehow and check for the remainder.
