5
$\begingroup$

The topologist J. H. C. Whitehead (not to be confused with his famous uncle) said it is naive to think a theorem is trivial merely because its proof is trivial. Hence I'm wondering if a certain trivial proposition appears in the literature somewhere. Maybe the best way to state it is this: If $p$ is the smallest prime factor of $n$ and $p^3>n$, then $n/p$ is prime.

Suppose I'm trying to factor $5497$ by hand. I've ruled out divisibility by all primes through $19$, and I do long division by $23$ and get $239$ as the quotient. Since all prime factors of $5497$ must be at least $23$, and $23^3$ is clearly too big to be $5497$, there's room for only one more prime factor, so I have to conclude that the quotient, $239$, is prime.

A standard step in standard algorithms appearing in all textbooks? Or somewhere else in published sources?

I suppose you could say I've tacitly ruled out divisibility of $239$ by all primes less than $\sqrt{239}$, and of course every (?) book mentions that, but I wasn't thinking of $239$ at the time, and I couldn't have reached my conclusion without going beyond the square root of $239$ and including $17$ and $19$ in my search.

  • 0
    A related thing is that if in the early stages of factoring a large number $n$, I see that $n$ is divisible by $2$ and by $7$, then I conclude that instead of searching primes up to $\sqrt{n}$, I only need to search as high as $\sqrt{n/14\;{}}$.2011-11-20

1 Answers 1

1

There should be many examples in the literature of this idea as a bound on the number of primes in the factorization of $n$, given the smallest prime or a lower bound on the prime factors, but probably there are very few examples where it is presented it as a primality condition, because of a lack of natural use cases where one would want to compare $p$ to a cube root and not a square root.

In the example from the question, the quotient $n/p$ is known before comparing $p^3$ with $n$. When the quotient is known, testing $p^3 > n$ is no easier than $p^2 > (n/p)$ because the relative error is the same in the two inequalities, which differ only by a factor of $p$. The required quality of approximation, or the cost of computation, would be higher for multiplying three times compared to twice.

Situations where the quotient is not known, but $p > \sqrt[3]{n}$ is known to be the smallest prime factor, are not immediately apparent. Of course it can be assumed, as in the exercise from Esmonde and Murty's book, but examples in nature are harder to find.

  • 1
    The formulation as a bound on number of prime divisors generalizes to all powers of $p$, while one cannot conclude primality of anything if $p$ is larger than the $R$th root of $n$ for R > 3. It also separates the issue of whether $p$ has been found to be a prime divisor of $n$ (by completing the long division) or is only a lower bound on prime divisors (as is known, or could be inferred, before the division begins, and is often discovered in the middle of a trial division).2011-11-19