Proving theorems and special cases (Part 2): The Pólya conjecture

In a recent class with my future secondary math teachers, we had a fascinating discussion concerning how a teacher should respond to the following question from a student:

Is it ever possible to prove a statement or theorem by proving a special case of the statement or theorem?

Usually, the answer is no… even checking many special cases of a conjecture does not mean that the conjecture is correct.

In yesterday’s post, we showed that the conjecture “ $n^2 - n + 41$ is a prime number for all positive integers $n$ ” is true for $1 \le n \le 40$ but fails for $n = 41$ . In today’s post, I’ll describe a conjecture that is true for plenty more special cases before becoming false.

The Pólya conjecture (see here and here for more information) stated that 50% or more of the natural numbers less than or equal to any given number have an odd number of prime factors (counting multiplicity). For example:

$2$ has one prime factor: odd

$3$ has one prime factor: odd

$4 = 2 \times 2$ has two prime factors: even

$5$ has one prime factor: odd

$6 = 2 \times 3$ has two prime factors: even

$7$ has one prime factor: odd

$8 = 2 \times 2 \times 2$ has three prime factors: odd

$9 = 3 \times 3$ has two prime factors: even

$10 = 2 \times 5$ has two prime factors: even

So of the numbers less than or equal to 10, five have an odd number of prime factors, and only four have an even number of prime factors.

The Pólya conjecture was first proven false by producing a counterexample in the vicinity of $1.845 \times 10^{361}$ . It turns out that the smallest counterexample is 906,150,257. In other words, the Pólya conjecture is true for the first 906,150,256 cases but fails on the next case.

Proving theorems and special cases (Part 1): Is n^2-n+41 always prime?

In a recent class with my future secondary math teachers, we had a fascinating discussion concerning how a teacher should respond to the following question from a student:

Is it ever possible to prove a statement or theorem by proving a special case of the statement or theorem?

Usually, the answer is no… even checking many special cases of a conjecture does not mean that the conjecture is correct.

The following example probably appears in every textbook that I’ve seen that handles mathematical induction to convince students that checking even many special cases of a conjecture is not sufficient for proving the conjecture.

Conjecture: If $n \ge 1$ is a positive integer, then $n^2 - n + 41$ is a prime number.

Is this true? Well, let’s start checking:

If $n = 1$ , then $n^2 - n + 41 = 1^2 - 1 + 41 = 41$ , which is a prime number.

If $n = 2$ , then $n^2 - n + 41 = 2^2 - 2 + 41 = 43$ , which is a prime number.

If $n = 3$ , then $n^2 - n + 41 = 3^2 - 3 + 41 = 47$ , which is a prime number.

If $n = 4$ , then $n^2 - n + 41 = 4^2 - 4 + 41 = 53$ , which is a prime number.

If $n = 5$ , then $n^2 - n + 41 = 5^2 - 5 + 41 = 61$ , which is a prime number.

If $n = 6$ , then $n^2 - n + 41 = 6^2 - 6 + 41 = 71$ , which is a prime number.

If $n = 7$ , then $n^2 - n + 41 = 7^2 - 7 + 41 = 83$ , which is a prime number.

If $n = 8$ , then $n^2 - n + 41 = 8^2 - 8 + 41 = 97$ , which is a prime number.

If $n = 9$ , then $n^2 - n + 41 = 9^2 - 9 + 41 = 113$ , which is a prime number.

If $n = 10$ , then $n^2 - n + 41 = 10^2 - 10 + 41 = 131$ , which is a prime number.

If $n = 11$ , then $n^2 - n + 41 = 11^2 - 11 + 41 = 151$ , which is a prime number.

If $n = 12$ , then $n^2 - n + 41 = 12^2 - 12 + 41 = 173$ , which is a prime number.

If $n = 13$ , then $n^2 - n + 41 = 13^2 - 13 + 41 = 197$ , which is a prime number.

If $n = 14$ , then $n^2 - n + 41 = 14^2 - 14 + 41 = 223$ , which is a prime number.

If $n = 15$ , then $n^2 - n + 41 = 15^2 - 15 + 41 = 251$ , which is a prime number.

If $n = 16$ , then $n^2 - n + 41 = 16^2 - 16 + 41 = 281$ , which is a prime number.

If $n = 17$ , then $n^2 - n + 41 = 17^2 - 17 + 41 = 313$ , which is a prime number.

If $n = 18$ , then $n^2 - n + 41 = 18^2 - 18 + 41 = 347$ , which is a prime number.

If $n = 19$ , then $n^2 - n + 41 = 19^2 - 19 + 41 = 383$ , which is a prime number.

If $n = 20$ , then $n^2 - n + 41 = 20^2 - 20 + 41 = 421$ , which is a prime number.

If $n = 21$ , then $n^2 - n + 41 = 21^2 - 21 + 41 = 461$ , which is a prime number.

If $n = 22$ , then $n^2 - n + 41 = 22^2 - 22 + 41 = 503$ , which is a prime number.

If $n = 23$ , then $n^2 - n + 41 = 23^2 - 23 + 41 = 547$ , which is a prime number.

If $n = 24$ , then $n^2 - n + 41 = 24^2 - 24 + 41 = 593$ , which is a prime number.

If $n = 25$ , then $n^2 - n + 41 = 25^2 - 25 + 41 = 641$ , which is a prime number.

If $n = 26$ , then $n^2 - n + 41 = 26^2 - 26 + 41 = 691$ , which is a prime number.

If $n = 27$ , then $n^2 - n + 41 = 27^2 - 27 + 41 = 743$ , which is a prime number.

If $n = 28$ , then $n^2 - n + 41 = 28^2 - 28 + 41 = 797$ , which is a prime number.

If $n = 29$ , then $n^2 - n + 41 = 29^2 - 29 + 41 = 853$ , which is a prime number.

If $n = 30$ , then $n^2 - n + 41 = 30^2 - 30 + 41 = 911$ , which is a prime number.

If $n = 31$ , then $n^2 - n + 41 = 31^2 - 31 + 41 = 971$ , which is a prime number.

If $n = 32$ , then $n^2 - n + 41 = 32^2 - 32 + 41 = 1033$ , which is a prime number.

If $n = 33$ , then $n^2 - n + 41 = 33^2 - 33 + 41 = 1097$ , which is a prime number.

If $n = 34$ , then $n^2 - n + 41 = 34^2 - 34 + 41 = 1163$ , which is a prime number.

If $n = 35$ , then $n^2 - n + 41 = 35^2 - 35 + 41 = 1231$ , which is a prime number.

If $n = 36$ , then $n^2 - n + 41 = 36^2 - 36 + 41 = 1301$ , which is a prime number.

If $n = 37$ , then $n^2 - n + 41 = 37^2 - 37 + 41 = 1373$ , which is a prime number.

If $n = 38$ , then $n^2 - n + 41 = 38^2 - 38 + 41 = 1447$ , which is a prime number.

If $n = 39$ , then $n^2 - n + 41 = 39^2 - 39 + 41 = 1523$ , which is a prime number.

If $n = 40$ , then $n^2 - n + 41 = 40^2 - 40 + 41 = 1601$ , which is a prime number.

Okay, a show of hands… did anyone actually carefully read and check the above 40 lines? I didn’t think so. The point is that the proposition works for $n = 1, 2, 3, \dots, 40$ . By about $n = 4$ , or so, a student (who didn’t already know the answer) actually did the above work would begin thinking, “Wow, this probably is correct for any value of $n$ .”

Of course, the catch happens at $n = 41$ :

If latex n = 41, then $n^2 - n + 41 = 41^2 - 41 + 41 = 41^2 = 41 \times 41$ ,

which is not a prime number.

All this to say, seeing a trend for the first few special cases… or the first few dozen special cases… does not necessarily mean that the trend will continue.

To prove that two things are equal, show that the difference is zero

The title of this post, “To prove that two things are equal, show that the difference is zero,” is surprisingly handy in the secondary mathematics curriculum. For example, it is the basis for the proof of the Mean Value Theorem, one of the most important theorems in calculus that serves as the basis for curve sketching and the uniqueness of antiderivatives (up to a constant).

And I have a great story that goes along with this principle, from 30 years ago.

I forget the exact question out of Apostol’s calculus, but there was some equation that I had to prove on my weekly homework assignment that, for the life of me, I just couldn’t get. And for no good reason, I had a flash of insight: subtract the left- and right-hand sides. While it was very difficult to turn the left side into the right side, it turned out that, for this particular problem, was very easy to show that the difference was zero. (Again, I wish I could remember exactly which question this was so that I could show this technique and this particular example to my own students.)

So I finished my homework, and I went outside to a local basketball court and worked on my jump shot.

Later that week, I went to class, and there was a great buzz in the air. It took ten seconds to realize that everyone was up in arms about how to do this particular problem. Despite the intervening 30 years, I remember the scene as clear as a bell. I can still hear one of my classmates ask me, “Quintanilla, did you get that one?”

I said with great pride, “Yeah, I got it.” And I showed them my work.

And, either before then or since then, I’ve never heard the intensity of the cussing that followed.

Truth be told, probably the only reason that I remember this story from my adolescence is that I usually was the one who had to ask for help on the hardest homework problems in that Honors Calculus class. This may have been the one time in that entire two-year calculus sequence that I actually figured out a homework problem that had stumped everybody else.

Another proof of the Law of Cosines

Source: https://www.facebook.com/AmerMathMonthly/photos/a.250425975006394.53155.241224542593204/755597884489198/?type=1&theater

Another proof of the Pythagorean theorem

Source: https://www.facebook.com/AmerMathMonthly/photos/a.250425975006394.53155.241224542593204/737392972976356/?type=1&theater

Proof without words: The difference of consecutive cubes

Source: https://www.facebook.com/photo.php?fbid=451328078334029&set=a.416585131808324.1073741827.416199381846899&type=1&theater

For a more conventional algebraic proof, notice that

$(n+1)^3 - n^3 = n^3 + 3n^2 + 3n + 1 - n^3 = 3n(n+1) + 1$

The product $n(n+1)$ is always an even number times an odd number: if $n$ is even, then $n+1$ is odd, but if $n$ is odd, then $n(n+1)$ . So $n(n+1)$ is a multiple of 2, and so $3n(n+1)$ is a multiple of 6. Therefore, $3n(n+1)+1$ is one more than a multiple of 6, proving the theorem.

Arithmetic with big numbers (Part 3)

In the previous two posts, we considered the use of base- $10^n$ arithmetic so that a calculator can solve addition and multiplication problems that it ordinarily could not handle. Today, we turn to division. Let’s now consider the decimal representation of $\displaystyle \frac{8}{17}$ .

There’s no obvious repeating pattern. But we know that, since 17 has neither 2 nor 5 as a factor, that there has to be a repeating decimal pattern.

So… what is it?

When I ask this question to my students, I can see their stomachs churning a slow dance of death. They figure that the calculator didn’t give the answer, and so they have to settle for long division by hand.

That’s partially correct.

However, using the ideas presented below, we can perform the long division extracting multiple digits at once. Through clever use of the calculator, we can quickly obtain the full decimal representation even though the calculator can only give ten digits at a time.

Let’s now return to where this series began… the decimal representation of $\displaystyle \frac{1}{7}$ using long division. As shown below, the repeating block has length $6$ , which can be found in a few minutes with enough patience. By the end of this post, we’ll consider a modification of ordinary long division that facilitates the computation of really long repeating blocks.

Because we arrived at a repeated remainder, we know that we have found the repeating block. So we can conclude that $\displaystyle \frac{1}{7} = 0.\overline{142857}$ .

Students are taught long division in elementary school and are so familiar with the procedure that not much thought is given to the logic behind the procedure. The underlying theorem behind long division is typically called the division algorithm. From Wikipedia:

Given two integers $a$ and $b$ , with $b \ne 0$ , there exist unique integers $q$ and $r$ such that $a = bq+r$ and $0 \le r < |b|$, where $|b|$ denotes the absolute value of $b$ .

The number $q$ is typically called the quotient, while the number $r$ is called the remainder.

Repeated application of this theorem is the basis for long division. For the example above:

Step 1.

$10 = 1 \times 7 + 3$ . Dividing by $10$ , $1 = 0.1 \times 7 + 0.3$

Step 2.

$30 = 4 \times 7 + 2$ . Dividing by $100$ , $0.3 = 0.04 \times 7 + 0.02$

Returning to the end of Step 1, we see that

$1 = 0.1 \times 7 + 0.3 = 0.1 \times 7 + 0.04 \times 7 + 0.02 = 0.14 \times 7 + 0.02$

Step 3.

$20 = 2 \times 7 + 6$ . Dividing by $1000$ , $0.02 = 0.002 \times 7 + 0.006$

Returning to the end of Step 2, we see that

$1 = 0.14 \times 7 + 0.02 = 0.14 \times 7 + 0.0002 \times 7 + 0.006 = 0.142 \times 7 + 0.006$

And so on.

By adding an extra zero and using the division algorithm, the digits in the decimal representation are found one at a time. That said, it is possible (with a calculator) to find multiple digits in a single step by adding extra zeroes. For example:

Alternate Step 1.

$1000 = 142 \times 7 + 6$ . Dividing by $1000$ , $1 = 0.142 \times 7 + 0.006$

Alternate Step 2.

$6000 = 587 \times 7 + 1$ . Dividing by $100000$ , $0.006 = 0.000587 \times 7 + 0.000001$

Returning to the end of Alternate Step 1, we see that

$1 = 0.142 \times 7 + 0.006= 0.142 \times 7 + 0.000587\times 7 + 0.000001 = 0.142857 \times 7 + 0.000001$

So, with these two alternate steps, we arrive at a remainder of $1$ and have found the length of the repeating block.

The big catch is that, if $a = 1000$ or $a = 6000$ and $b = 7$ , the appropriate values of $q$ and $r$ have to be found. This can be facilitated with a calculator. The integer part of $1000/7$ and $6000/7$ are the two quotients needed above, and subtraction is used to find the remainders (which must be less than $7$ , of course).

At first blush, it seems silly to use a calculator to find these values of $q$ and $r$ when a calculator could have been used to just find the decimal representation of $1/7$ in the first place. However, the advantage of this method becomes clear when we consider fractions who repeating blocks are longer than 10 digits.

Let’s now return to the question posed at the top of this post: finding the decimal representation of $\displaystyle \frac{8}{17}$ . As noted in Part 6 of this series, the length of the repeating block must be a factor of $\phi(17)$ , where $\phi$ is the Euler toitent function, or the number of integers less than $17$ that are relatively prime with $17$ . Since $17$ is prime, we clearly see that $\phi(17) = 16$ . So we can conclude that the length of the repeating block is a factor of $16$ , or either $1$ , $2$ , $4$ , $8$ , or $16$ .

Here’s the result of the calculator again:

We clearly see from the calculator that the repeating block doesn’t have a length less than or equal to $8$ . By process of elimination, the repeating block must have a length of $16$ digits.

Now we perform the division algorithm to obtain these digits, as before. This can be done in two steps by multiplying by $10^8 = 100,000,000$ .

So, by the same logic used above, we can conclude that

$\displaystyle \frac{8}{17} = 0.\overline{4705882352941176}$

In other words, through clever use of the calculator, the full decimal representation can be quickly found even if the calculator itself returns only ten digits at a time… and had rounded the final $2941176$ of the repeating block up to $3$ .

(Note: While this post continues exploring the unorthodox use of a calculator to handle arithmetic problems, it also appeared in a previous series on the decimal expansions of rational numbers.)

Proof without words: A relation between the sides of a right trapezoid

Source: https://www.facebook.com/photo.php?fbid=494947463972090&set=a.416585131808324.1073741827.416199381846899&type=1&theater

Inverse Functions: Logarithms and Complex Numbers (Part 30)

Ordinarily, there are no great difficulties with logarithms as we’ve seen with the inverse trigonometric functions. That’s because the graph of $y = a^x$ satisfies the horizontal line test for any $0 < a < 1$ or $a > 1$ . For example,

$e^x = 5 \Longrightarrow x = \ln 5$ ,

and we don’t have to worry about “other” solutions.

However, this goes out the window if we consider logarithms with complex numbers. Recall that the trigonometric form of a complex number $z = a+bi$ is

$z = r(\cos \theta + i \sin \theta) = r e^{i \theta}$

where $r = |z| = \sqrt{a^2 + b^2}$ and $\tan \theta = b/a$ , with $\theta$ in the appropriate quadrant. This is analogous to converting from rectangular coordinates to polar coordinates.

Over the past few posts, we developed the following theorem for computing $e^z$ in the case that $z$ is a complex number.

Definition. Let $z = r e^{i \theta}$ be a complex number so that $-\pi < \theta \le \theta$ . Then we define

$\log z = \ln r + i \theta$ .

Of course, this looks like what the definition ought to be if one formally applies the Laws of Logarithms to $r e^{i \theta}$ . However, this complex logarithm doesn’t always work the way you’d think it work. For example,