4
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ You may be interested by divisibility rules. $\endgroup$ – Harry49 Oct 3 '17 at 7:51
  • 1
    $\begingroup$ The general rule is to test whether or not the value of $N/M$ is integer. $\endgroup$ – goodvibration Oct 3 '17 at 7:56
  • 6
    $\begingroup$ Factoring is one of the hardest task and requires exponential time. On the difficulty of this task is based public key criptography, where large primes (500 digit primes I mean) are multiplied and factoring requires more than the age of universe even with the most powerful supercomputer. Urban legends tells the story of quantum computers which could theoretically factor these numbers in minutes. Google invested several million $ and they get the quite amazing result to factor 143.... $\endgroup$ – Raffaele Oct 3 '17 at 8:01
  • 6
    $\begingroup$ For a given $M$ you can just do long division. It is not very time consuming. The problem in factoring is that there are so many possible $M$s, not that checking an individual one is slow. $\endgroup$ – Ross Millikan Nov 29 '17 at 1:38
  • 1
    $\begingroup$ The question is not clear to me. Is $M$ given? If not, is $y$ given? $\endgroup$ – Paul Dec 3 '17 at 22:20
2
+50
$\begingroup$

The method below is good for small values $y$. Say, for $y\le 12$.
And it is closely related to divisibility rules.

Explained via example:
let

$$N = 1529773658514887677106240187604962388655195023566;$$ $$M=14159.$$

Since $y=5$, we group digits of the number $N$ by $5$: $$N = \color{gray}{0}1529\;\;77365\;\;85148\;\;87677\;\;10624\;\;01876\;\;04962\;\;38865\;\;51950\;\;23566;\tag{1}$$ and rewrite $N$ as $$N = a_9\cdot 100000^9 + a_8 \cdot 100000^8 + \cdots + a_1 \cdot 100000 + a_0,\tag{2}$$ where $0\le a_j < 100000$.

We'll find number $v$ ($0\le v < 100000$), for which $$N \equiv v (\bmod M).\tag{3}$$ If $v=0$, then $N$ is divisible by $M$.

So, we find remainders of $10000$, $10000^2$, $\ldots$, $10000^9$ first: \begin{array}{rcr} 100000 &\equiv &\color{darkred}{887} (\bmod 14159),\\ 100000^2\equiv 887\cdot 887=786769 &\equiv &\color{darkred}{8024} (\bmod 14159),\\ 100000^3\equiv 887\cdot 8024=7117288 & \equiv &\color{darkred}{9470} (\bmod 14159),\\ & \cdots & \\ 100000^8 &\equiv &\color{darkred}{11965} (\bmod 14159),\\ 100000^9 &\equiv &\color{darkred}{7864} (\bmod 14159). \end{array}

Therefore \begin{array}{r}N \equiv 01529\cdot \color{darkred}{7864} \\ + 77365 \cdot \color{darkred}{11965} \\ + \cdots \quad\\ + 04962 \cdot \color{darkred}{9470} \\ + 38865 \cdot \color{darkred}{8024} \\ + 51950 \cdot \color{darkred}{887} \\ + 23566 \cdot \color{darkred}{1} \\ \equiv 0 (\bmod 14159). \end{array} So, $N$ is divisible by $M$.


Relation to divisibility rules:
if $M=3$, then $y=1$, and we note that $$10\equiv 1 (\bmod 3);\\ 10^2\equiv 1 (\bmod 3);\\ 10^3\equiv 1 (\bmod 3);\\ \cdots$$ and for $$N=a_j\cdot 10^j + a_{j-1}\cdot 10^{j-1}+\cdots + a_1\cdot 10 + a_0$$ we have $$N\equiv a_j + a_{j-1}+\cdots + a_1 + a_0 (\bmod 3)$$ (iif $N$ is divisible by $3$ then sum of its digits is divisible by $3$).

$\endgroup$
1
$\begingroup$

You ask two or three questions:

  1. 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).

  1. 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.

  1. 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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.