Putnam 1998, Problem B-6

Prove that, for any integers \( a, b, c \), there exists a positive integer \( n \) such that \( \sqrt{n^3 + an^2 + bn + c} \) is not an integer.


Solution:
First solution: Write \( p(n) = n^3 + an^2 + bn + c \). Note that \( p(n) \) and \( p(n + 2) \) have the same parity, and recall that any perfect square is congruent to \( 0 \) or \( 1 \pmod{4} \). Thus if \( p(n) \) and \( p(n + 2) \) are perfect squares, they are congruent \( \pmod{4} \). But \( p(n + 2) - p(n) \equiv 2n^2 + 2b \pmod{4} \), which is not divisible by \( 4 \) if \( n \) and \( b \) have opposite parity.

Second solution: We prove more generally that for any polynomial \( P(z) \) with integer coefficients which is not a perfect square, there exists a positive integer \( n \) such that \( P(n) \) is not a perfect square. Of course it suffices to assume \( P(z) \) has no repeated factors, which is to say \( P(z) \) and its derivative \( P'(z) \) are relatively prime.

In particular, if we carry out the Euclidean algorithm on \( P(z) \) and \( P'(z) \) without dividing, we get an integer \( D \) (the discriminant of \( P \)) such that the greatest common divisor of \( P(n) \) and \( P'(n) \) divides \( D \) for any \( n \). Now there exist infinitely many primes \( p \) such that \( p \) divides \( P(n) \) for some \( n \): if there were only finitely many, say \( p_1, \ldots, p_k \), then for any \( n \) divisible by \( m = P(0)p_1p_2\cdots p_k \), we have \( P(n) \equiv P(0) \pmod{m} \), that is, \( P(n)/P(0) \) is not divisible by \( p_1, \ldots, p_k \), so must be \( \pm 1 \), but then \( P \) takes some value infinitely many times, contradiction. In particular, we can choose some such \( p \) not dividing \( D \), and choose \( n \) such that \( p \) divides \( P(n) \). Then \( P(n + kp) \equiv P(n) + kpP'(n) \pmod{p} \) (write out the Taylor series of the left side); in particular, since \( p \) does not divide \( P'(n) \), we can find some \( k \) such that \( P(n + kp) \) is divisible by \( p \) but not by \( p^2 \), and so is not a perfect square.

Third solution: (from David Rusin, David Savitt, and Richard Stanley independently) Assume that \( n^3 + an^2 + bn + c \) is a square for all \( n > 0 \). For sufficiently large \( n \),
\[
\left(n^{3/2} + \frac{1}{2} an^{1/2} - 1\right)^2 < n^3 + an^2 + bn + c < \left(n^{3/2} + \frac{1}{2} an^{1/2} + 1\right)^2;
\]
thus if \( n \) is a large even perfect square, we have \( n^3 + an^2 + bn + c = \left(n^{3/2} + \frac{1}{2} an^{1/2}\right)^2 \). We conclude this is an equality of polynomials, but the right-hand side is not a perfect square for \( n \) an even non-square, contradiction. (The reader might try generalizing this approach to arbitrary polynomials. A related argument, due to Greg Kuperberg: write \( \sqrt{n^3 + an^2 + bn + c} \) as \( n^{3/2} \) times a power series in \( 1/n \) and take two finite differences to get an expression which tends to \( 0 \) as \( n \to \infty \), contradiction.)

Note: in case \( n^3 + an^2 + bn + c \) has no repeated factors, it is a square for only finitely many \( n \), by a theorem of Siegel; work of Baker gives an explicit (but large) bound on such \( n \). (I don't know whether the graders will accept this as a solution, though.)