2
$\begingroup$

If I want to divide $9251$ by $29$, the methods taught in elementary school suffice.

Now suppose I want the prime factorization of $9251$. The square root of that number is between the consecutive primes $89$ and $97$, so I decide to check for divisibility by $$ 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89, $$ except that of course I might finish factoring the number long before I get to $89$.

Lo and behold, I find it to be divisible by $11$ and by $29$. So it's $$ 9251 = 11\times29\times(\text{ ? }), $$ and of course the number "$(\text{ ? })$" is $\dfrac{9251}{11\times29}$, which I could find by old-fashioned long division if I felt like it. But I go on checking for divisibility by $31,37,41,\ldots,89$, and find it's divisible by none of those!

Conclusion: The quotient "$(\text{ ? })$" must be either $11$ or $29$ and $11$ is clearly too small, and let's suppose I was not so absent-minded when I checked $11$ that I omitted to rule out $11^2$, as I later was with $29$, so it must be $29$.

My question: Now suppose we're working with numbers with many thousands of digits, with a computer. Would there ever be an occasion where it's more efficient or otherwise better to find the quotient by the means described here than by pedestrian methods taught in fourth grade or by straighforward-even-if-sophisticated elaborations of those?

$\endgroup$
1
$\begingroup$

For computers, division is a straightforward problem that can be done quickly, while factorization is a hard problem with no known fast method. I believe it would be much harder for computers to try to factor numbers just for division, as hardware and low level instructions are optimized for division (there are in fact algorithms that can divide faster than long division).

$\endgroup$
  • $\begingroup$ When I wrote "straighforward-even-if-sophisticated elaborations of those" I meant of course what you call "algorithms that can divide faster than long division". However, I did not have in mind factoring just for the purpose of division, but rather doing a division problem in that way when one is factoring. So factoring is the purpose and division is one of the things that serve the purpose. $\endgroup$ – Michael Hardy Feb 5 '14 at 2:37
  • $\begingroup$ I'm still not understanding what's being asked. Of course there needs to be division for factoring. Once a factor has been found, it's logical to start over and look for small factors again that divide that factor? $\endgroup$ – qwr Feb 5 '14 at 2:44
  • $\begingroup$ I'm saying that in searching for that last factor, one eliminates all the possibilities except $29$ and consequently concludes that it's $29$, and I'm asking whether there may be circumstances in which that's the most efficient way to do it, or where there may otherwise be some reason to do it that way. $\endgroup$ – Michael Hardy Feb 5 '14 at 4:38

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.