# A trivial but maybe nonetheless non-trivial method of inferring primality

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.

-
This appears as exercise 1.1.10 in Problems in Algebraic Number Theory by Murty and Esmonde. You can find it on page 5 here. – JSchlather Nov 19 '11 at 20:29
Analogous inferences hold in Euclidean domains, e.g. if a quintic polynomial has a quadratic factor but no linear factors then its cubic cofactor is prime (irreducible). – Bill Dubuque Nov 19 '11 at 21:11
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\;{}}$. – Michael Hardy Nov 20 '11 at 17:07

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.
You wrote: "the quotient $n/p$ is known before comparing $p^3$ with $n$". I don't think that's right. Before the quotient is computed, one already knows that if the remainder is $0$, then the quotient will be prime. Would anyone doing this fail to notice that $23^3$ is too big, before actually doing the division? – Michael Hardy Nov 19 '11 at 22:50
In your example the division is completed ("I do long division by 23 and get 239 as the quotient") before further analysis occurs. Something cubed being "too big" occurs at an earlier stage once the trial value of $p$ exceeds 17 (and could be seen before the attempted $p$ gets to 23) so the more natural logic is to say that at some stage of the calculation, possibly prior to commencing the long division, one knows that $n$ has at most two prime factors. It is from this fact, however one arrived at it, that divisibility by 23 implies the other factor is prime. Cube rt argument is secondary. – zyx Nov 19 '11 at 23:15
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). – zyx Nov 19 '11 at 23:32