# Odd way to do arithmetic

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?

• 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. – Michael Hardy Feb 5 '14 at 4:38