Odd way to do arithmetic

79 Views Asked by At

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?

1

There are 1 best solutions below

3
On

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