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.

  • 6
    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](http://books.google.com/books?id=R_e8JufiH5cC&lpg=PR4&dq=Problems%20in%20algebraic%20number%20theory&pg=PA5#v=onepage&q=Problems%20in%20algebraic%20number%20theory&f=false).2011-11-19
  • 3
    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).2011-11-19
  • 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