# Is $n^2-79n+1601$ composite? Proof by cases…

If one case is true but the other false, does that mean that the statement is true or false?

There exists a positive integer $n$ such that $n^2-79n+1601$ is composite

• Case 1 - $n$ is even - false.
• Case 2 - $n$ is odd - true.
-
If the statement is "in all cases, blah happens" then the statement is false. If the statement is "in some cases, blah happens", then it is true. If the statement is "there is an object that has property blah", and you show that there is an object that sometimes has the property, and sometimes doesn't, you haven't proved that the statement is true or false, your argument does not work in this case. –  Andres Caicedo Dec 11 '10 at 20:10

It is not appropriate to use proof by cases here. The statement, "There exists a positive integer n such that $n^2−79n+1601$ is composite" means exactly what it says. It states that there is at least one positive integer that makes this statement true. It is no different from any other similar statement such as "I have at least one dollar in my pocket". All I have to do to prove this is reach into my pocket and show you the dollar.

All you have to do to show your original proposition is to find one number, that makes it true. Being too abstract is counterproductive here. You can find one number such as 1601. Then, you just have to do the computations that show that the number produced is composite. Literally, the same computations you might do in grade school. In the case of 1601,

$$1601^2-79\times1601+1601$$

gives a number that is clearly composite, which is why I picked it.

-
CLEARY 2,438,323 is composite –  Trevor Arjeski Dec 12 '10 at 15:58
@TrevorMA: $1601^2-79\times1601+1601=1601\times(1601-79+1)=1601\times1523$ –  Henry B. Dec 12 '10 at 18:50

The statement you give in your example doesn't really have cases. It is true if some such integer exists, and false otherwise. I don't know what your cases are supposed to mean, because there are both odd and even examples showing that the statement is true. However, you only need to give one example.

As for actually proving this, a hint is that you can look for a value of $n$ such that the 3 terms in your expression have a common factor.

-

HINT $\$ The polynomial takes many successive prime values because it is Euler's famous prime generating polynomial $\rm\ x^2 + x + 41\$ shifted by $\rm\ x\to x - c\$ for $\rm\ c = \ldots$

-

The statement is that there exists some positive integer $n$ such that $n^2 - 79n + 1601$ is composite. You need to find only one $n$ for this to be a true statement. To prove the statement is false, you would need to show that $n^2 - 79n + 1601$ is prime for all $n$.

It turns out the statement is true, but not for all odd $n$. Take $n = 1$, for example. $1 - 79 + 1601 = 1523$, which is prime. I'll leave it to you to find $n$ such that the expression is composite.

-
I dont know how to prove the statement. Should I negate it and prove the negation? –  Trevor Arjeski Dec 11 '10 at 20:17
That would prove the statement is false. To prove it is true, you need find only one integer that satisfies it. –  Hans Parshall Dec 11 '10 at 20:19
I don't know what you are saying, Trevor. If you have to prove a statement, how can you possibly prove the negation? –  Andres Caicedo Dec 11 '10 at 20:20
It says prove or disprove.. –  Trevor Arjeski Dec 11 '10 at 20:21
@TrevorMA: In order to prove that a statement that says "there exists $n$ such that..." is true, you only need to find one specific $n$ for which the statement is true. For example, "There exists an integer $n$ such that $n$ is greater than 100" is true, and we prove it is true by exhibiting an $n$ with the property: "Take $n=101$; it is an integer, and is greater than 100, so the statement is true." In order to prove that a statement "There exists $n$ such that..." is false, you need to prove that for all $n$, the "such that" statement is false (cont) –  Arturo Magidin Dec 11 '10 at 20:41

Trevor, you are confusing what is generally thought of as "Proof by cases", and a search for an example that proceeds by narrowing the possibilities/examining different cases.

A Proof by Cases is one that proceeds along the following lines: you want to show that a statement is true for all $x$, but you do so by first breaking up all the possible $x$'s into different "camps", and then showing the property holds in each "camp". For instance, take

For all real numbers $x$, $|x|\geq 0$.

Now, since the absolute value is defined as $$|x|=\left\{\begin{array}{ll} x & \mbox{if x\gt 0,}\\ -x & \mbox{if x\leq 0.}\\ \end{array}\right.$$ then we can proceed in the proof by cases: every real number $x$ is either positive, or less than or equal to zero. We examine each possibility separately, and if the conclusion holds in each of them, we'll know that the conclusion always holds (since every real number is in one of the two camps, and everyone in each of the camps has the desired property). If $x\gt 0$. then $|x|=x\gt 0$, and if $|x|\gt 0$, then $|x|\geq 0$ is also true. So the conclusion holds for the gang of positive numbers. If $x\leq 0$, then $|x|=-x$, and since $x\leq 0$, then $-x\geq 0$, so $|x|\geq 0$. Thus, the conclusion also holds for elements of the "other" gang, the nonpositives. Since every real number belongs to either the Positives or the Nonpositives, and every positive has the desired property and every nonpositive has the desired property, then every real number has the desired property.

That's a Proof by cases.

You can also do a "proof by cases" to show that something is false; but in that case, you are usually trying to negate an existential statement, such as "There exists an integer $n$ such that $2n=1$." You could say: "every integer is either even or odd; if $n$ is even, then $2n$ is a multiple of an even number $n$, so it is even, hence not equal to $1$. If $n$ is odd, then $2n$ is a multiple of $2$, which is even, so $2n$ is even, hence not equal to $1$. Since no even number has the property, no odd number has the property, and every integer is either even or odd, then no integer has the property; the statement is false" (It's a bit convoluted, and you don't need to do it by cases, but hopefully you see the idea). In fact, you are really proving the negation, "For all integers $n$, $2n\neq 1$," so it is the same as the previous example.

By contrast, what you have here is an existential statement: it says "there is an integer $n$ with a property." In order to prove that the statement is false, you could proceed by cases as above; but in order to prove that the statement is true, what you need to do is produce a single integer $n$ for which the condition holds. Your answer, if the statement is true, should be of the form: "Take $n=xx$; this integer has the property", followed by the computations to justify the assertion that it has the property (in this case, you would plug it into $n^2 -79n + 1601$, compute the answer, and then factor the answer to show it is composite.

As you search for an $n$ for which the property will hold, you don't want to examine every possible integer until you hit one that works; because you may run the risk that it takes a long time to hit the first example (or maybe there isn't one? Just because you haven't found one after searching for a long time, you don't know if that's because there isn't an example, or because there is an example but is much bigger than what you've checked so far). So you are certainly smart to consider different possibilities for $n$ to see how they behave; e.g., if $n$ is even, then the expression does not have any obvious factors; if $n$ is a multiple of $3$, does it have any obvious factors? And so on. But that's not a "proof by cases", because in the end your proof will be of the form: "Here is an $n$ with the property", and not a case-by-case analysis.

Did that make sense and help? Feel free to ask questions, I can add to the answer to clarify or give other examples.

-

It may actually be worth pointing out that if $p(x)$ is a polynomial with integer coefficients, the only way $p(n)$ is never composite as $n$ varies over the integers is if $p$ is constant (and $p(x)=c$ for some $c$ that is either prime, the negative of a prime, $1$, or $-1$).

For suppose that $p(x)=ax^n+bx^{n-1}+\dots+c$. Then clearly $c$ divides $p(c)$. Also, $c$ divides $p(2c)$, $p(3c)$, etc.

Suppose first $|c|>1$. The only way we do not find a composite number in the list $p(c),p(2c),p(3c),\dots$ is if all these numbers are $c$ or $-c$ and $c$ or $-c$ itself is prime. But then infinitely many of the $p(nc)$ are equal to each other. But polynomials that take the same value too often are constant.

If $c=0$, we are done because $p(0)=0$ is composite.

So, finally, suppose that $|c|=1$.

Write $p(x)=\alpha(x-1)^n+\beta(x-1)^{n-1}+\dots$, $p(x)=A(x-2)^n+B(x-2)^{n-1}+\dots$, etc. If at least one of these expansions has constant term of absolute value larger than 1, and we are done by the previous analysis, or else all of them have constant term $1$, $-1$, or $0$. Note that the constant term in the first case is $p(1)$, in the second is $p(2)$, etc. So again we have that either $p(n)=0$ for some $n$ (and so it is composite), or else $p$ takes the same value ($1$ or $-1$) infinitely often, and we conclude that $p$ is constant.

-