4
$\begingroup$

Let $n$ be an integer and show that $q(n)=11n^2 + 32n$ is a prime number for two integer values of $n$, and is composite for all other integer values of $n$.

$\endgroup$
2
  • 2
    $\begingroup$ I think that you need to allow negative integer values of $n$ as well. (If I'm not mistaken, there is only one positive integer value of $n$ for which $q(n)$ is prime.) $\endgroup$
    – Matt E
    Commented May 3, 2011 at 0:32
  • $\begingroup$ Oh sorry you're right, wrote the question incorrectly! $\endgroup$
    – meiryo
    Commented May 3, 2011 at 0:35

4 Answers 4

11
$\begingroup$

Hint: Factor $q(n)$ into 2 distinct polynomials. If both polynomials have values other than $\pm 1$, then you know that $q(n)$ cannot be prime. From this, determine what the only values of $n$ are that could possibly result in $q(n)$ being prime and check the cases.

$\endgroup$
2
  • $\begingroup$ So the answer would be $n=-3,1$? $\endgroup$
    – meiryo
    Commented May 3, 2011 at 0:58
  • $\begingroup$ @meiryo: That's correct. $\endgroup$
    – bzc
    Commented May 3, 2011 at 1:17
5
$\begingroup$

HINT $\ $ If $\rm\:f(x) = g(x)\:h(x)\:$ is composite then it has only finitely many prime values since such requires $\rm\:g(x) = \pm 1\:$ or $\rm\:h(x) = \pm 1\:.$ But $\rm\:f(x)\pm 1 = 0\:$ has no more than $\rm\:deg\ f\:$ roots.

Following are some related results. In 1918 Stackel published the following simple

THEOREM If $\rm\:p(x)\:$ is a composite integer coefficient polynomial then $\rm\:p(x)\:$ is composite for all $\rm\:|x| > b\:,\:$ for some bound $\rm\:b\:,\:$ in fact $\rm\:p(x)\:$ has at most $\rm\:2\:d\:$ prime values, where $\rm\: d = deg\ p\:.\:$

The simple proof can be found online in Mott & Rose, p.8. I highly recommend this delightful and stimulating 27 page paper which discusses prime-producing polynomials and related topics.

Contrapositively, $\rm\:p(x)\:$ is prime (irreducible) if it assumes a prime value for large enough $\rm\:|x|\:.\:$ Conversely Bouniakowski conjectured (1857) prime $\rm\:p(x)\:$ assume infinitely many prime values (except in trivial case where values of $\:p\:$ have a common divisor, e.g. $\rm\ 2\ |\ x(x+1)+2\:$ ).

E.g. Polya-Szego popularized A. Cohn's irreduciblity test, which says that an integer coefficient polynomial $\rm\:p(x)\:$ is irreducible if $\rm\:p(b)\:$ yields a prime in radix $\rm\:b\:$ representation, i.e. $\rm\:0 \le p_i < b\:.\:$

E.g. $\rm\:f(x) = x^4 + 6 x^2 + 1\:$ factors $\rm\:(mod\ p)\:$ for all primes $\rm\:p\:,\:$ yet $\rm\:f(x)\:$ is prime since we have that $\rm\:f(8) = 10601\:$ octal $\rm = 4481\:$ is prime.

Note: Cohn's irreducibility test fails if, in radix $\rm\:b\:,\:$ negative digits are allowed, e.g. $\rm\:f(x) = x^3 - 9 x^2 + x-9 = (x-9)\ (x^2 + 1)\:$ but $\rm\:f(10) = 101\:$ is prime.

For more see my 2002-11-12 sci.math post, and Murty's paper.

$\endgroup$
3
$\begingroup$

Write it as $q(n) = n(11n+32)$. $q(1) = 43$ is prime, and $q(-3) = 3$ is prime. $q(-2), q(-1)$ and $q(0)$ are not prime. But if $n < -3$ or $n > 1$, $|n| > 1$ and also $|11*n+32| > 1$, so $q(n)$ is composite.

$\endgroup$
2
  • 2
    $\begingroup$ $n \mid q(n)$ is not enough to imply that $q(n)$ is not prime. In particular, consider $n=-3$. $\endgroup$
    – bzc
    Commented May 3, 2011 at 0:47
  • $\begingroup$ The question has been edited to allow non-positive values of n. But the same reasoning works for all n < -3. $\endgroup$ Commented May 3, 2011 at 1:33
2
$\begingroup$

Hint: We know how to factor q, as we can write it as $q(n) = n(11n + 32)$. So n will always divide $q(n)$ - I wonder what that could tell us?

I should note that if this is a homework question, you should tag it as such.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .