Lecture 28 - Math in Pop Culture

Summary

We started class by introducing the play Proof. Proof, written by David Auburn and published in 2001, deals with three mathematicians: a mathematics Professor, his daughter, and his former student. The class read two scenes aloud that gave way to our first two topics. The first scene was an argument between the Professor and his daughter about how many days she has wasted. After some back and forth, they realize that she has wasted a little over 33 days, which, if treated as years, and then converted to weeks, equals 1729 weeks. This number is special because it is expressible as the sum of two cubes in two different ways. Wael showed us a theorem showing how to characterize numbers that are the sums of two cubes. The second scene from the play that the class read aloud was about the daughter and the former student discussing mathematics conferences. The daughter tells Sophie Germain's story, which leads into our second theorem below presented by Jen, regarding when Germain primes occur.[1]
Afterwards, Tom discussed a conversation from the television show Bones in which the topic of perfect numbers came up. He followed with some brief history of perfect numbers, by proving and disproving some claims by Nicomachus, and following up with a neat characteristic of perfect numbers.

Characterizing the sum of two cubes

Theorem: Let $n \in \mathbb{Z^+}$. Then $\exists \;\; x,y \in \mathbb{Z^+}$ satisfying the equation $n=x^3+ y^3$ if and only if conditions (a), (b) and (c) are satisfied:

  • (a) $\exists \;\; m \in \mathbb{Z^+}$ such that $m \mid n$ and $n^{1/3} \le m \le 2^{2/3} \cdot n^{1/3}$ such that,
  • (b) $\exists \;\; k \in \mathbb{Z^+}$ such that $m^2 - \frac{n}{m} = 3k$ such that,
  • (c) $m^2 - 4k$ is a perfect square.

Proof: $( \; \Longrightarrow \;)$ Let $n = u^3 + v^3$ with $n,u,v \in \mathbb{Z^+}$. We need to show that the three conditions (a), (b) and (c) are satisfied.
We have that $n = u^3 + v^3 = (u+v)(u^2 - uv+v^2)$. Letting $m = u+v$, then $m \in \mathbb{Z^+}$ and $m \mid n$ so we need to verify that $n^{1/3} \le m \le 2^{2/3} \cdot n^{1/3}$ in order to prove that (a) is satisfied. Notice that

(1)
\begin{align} u^2 - uv + v^2 = \frac{n}{m} \end{align}
(2)
\begin{equation} u + v = m \end{equation}

so it can be easily seen that the point $(u,v)$ satisfy the following two equations

(3)
\begin{align} x^2 - xy + y^2 = \frac{n}{m} \end{align}
(4)
\begin{equation} x+y = m \end{equation}

Now let's treat both equations geometrically. The second equation is an equation of a line with a slope of $-1$. For the first equation, we know that the general equation for a conic section is

(5)
\begin{equation} ax^2 + bxy + cy^2 + dx + ey = f \end{equation}

and that equation represents an Ellipse if and only if $f \neq 0$ and $f\cdot (b^2 - 4ac) < 0$. In Equation (3), we have that $a=1, b=-1, c=1, d=0, e=0, f=\frac{n}{m}$ so we can deduce that $f = \frac{n}{m} \neq 0$ because $n,m \in \mathbb{Z^+}$ so dividing them will result always in a positive real number. Moreover, $f\cdot (b^2-4ac) = \frac{n}{m} \cdot(1 - 4(1)(1)) = - \frac{3n}{m} < 0$ so we conclude that Equation (3) represents an Ellipse. It can be shown that this Ellipse has a major axis lying on the line $y=x$ which has a slope of $+1$ (showing that requires cumbersome computations, and it can be easily checked with graphing programs so we will avoid it here).

Now, we know that the point $(u,v)$ satisfies both Equations (3) and (4), and that $u$ and $v$ are both positive, so the point $(u,v)$ lies on the first quadrant, and so the line in Equation (4) intersects with the ellipse in Equation (3) in the first quadrant only. Observe also that the lines $x+y=m$ and $y=x$ are perpendicular since their slopes' product is $(+1) \times (-1) = -1$. Using those two observations we can sketch the following graph

Ellipse.jpg

In the graph above, it should be clear that the line $x+y=m$ (represented by the dashed line) has no fixed place, but we are sure that it lies somewhere on or between the parallel lines $L_1$ and $L_2$ (and parallel to them) since it must intersect with the Ellipse in the first quadrant. Now, we know that the line $x+y=m$ will cut the $x$-axis when $y=0$ and that implies $x=m$. We also know that the ellipse will cut the $x$-axis when $y=0$ and that implies $x=\sqrt{\frac{n}{m}}$. Since the line will cut the $x$-axis on the point $A$ or beyond, we deduce

(6)
\begin{align} \sqrt{\frac{n}{m}} \le m \Longrightarrow \frac{n}{m} \le m^2 \Longrightarrow n^{1/3} \le m \end{align}

Now, since the line $x+y=m$ never exceeds the line $L_2$, so the distance from the origin $(0,0)$ to the line $x+y=m$ is less than or equal to the semi-major axis of the Ellipse (which is the line segment $\overline{OB}$). To calculate the distance from the origin to the line $x+y=m$ we use the general equation of calculating the distance from a point $(x_1,y_1)$ to the line $ax+bx+c=0$ which is

(7)
\begin{align} D = \frac{|a\cdot x_1 + b \cdot y_1 + c|}{\sqrt{a^2 + b^2}} = \frac{|1\cdot (0) + 1 \cdot (0) + (-m)|}{\sqrt{1^2+1^2}} = \frac{m}{\sqrt2} \end{align}

we also can deduce (from the properties of ellipses and the Pythagorean Theorem) that the semi-major axis has a length of

(8)
\begin{align} |OB|^2 = \left( \sqrt{\frac{n}{m}} \right)^2 + \left( \sqrt{\frac{n}{m}} \right)^2 \Longrightarrow |OB| = \sqrt{2} \cdot \sqrt{\frac{n}{m}} \end{align}

we conclude that

(9)
\begin{align} D \le |OB| \Longrightarrow \frac{m}{\sqrt2} \le \sqrt{2} \cdot \sqrt{\frac{n}{m}} \Longrightarrow \frac{m^2}{2} \le 2 \cdot \frac{n}{m} \Longrightarrow m^3 \le 2^2 \cdot n \Longrightarrow m \le 2^{2/3} \cdot n^{1/3} \end{align}

combining (6) and (9), we get

(10)
\begin{align} n^{1/3} \le m \le 2^{2/3} \cdot n^{1/3} \end{align}

so condition (a) is satisfied.

For condition (b), note that $m^2 - \frac{n}{m} = (u+v)^2 - (u^2 -uv +v^2) = 3uv$, letting $k=uv \in \mathbb{Z^+}$ we see that condition (b) is satisfied.

For condition (c), note that $m^2 - 4k = (u+v)^2 -4uv = (u-v)^2 \in \mathbb{Z^+}$ so $m^2 -4k$ is a perfect square, so condition (c) is satisfied.

$( \Longleftarrow )$ Suppose that conditions (a), (b) and (c) are satisfied and let's prove that $n = x^3 + y^3$ for some positive integers $x$ and $y$. Define $m$ as in (a), let $k$ be a positive integer satisfying $m^2 - \frac{n}{m} = 3k \Longrightarrow \frac{n}{m} = m^2 - 3k$ as in (b), and let $m^2 - 4k$ be a perfect square as in (c).

Now, let's examine the equation $x^2 -mx + k=0$. This equation has a determinant $\Delta = m^2 - 4k$, and that's a perfect square, thus $\exists \; s \in \mathbb{Z}$ such that $m^2-4k=s^2$. Now consider the two solutions (let's call them $u$ and $v$) of the equation $x^2 -mx+k=0$. Using the general method of solving quadratic equations, we get

(11)
\begin{align} u = \frac{m + s}{2} , \; \; v = \frac{m-s}{2} \end{align}

(where $u$ and $v$ can be switched) Now, consider the parity of $m$ and $s$. We have that $m$ is either $\text{even}$ or $\text{odd}$. If $m = \text{odd}$ then by $s = \sqrt{m^2 - 4k}$ we get that the parity of $s$ is

(12)
\begin{align} \sqrt{ (\text{odd})^2 - \text{even} } = \sqrt{ \text{odd} - \text{even} } = \sqrt{\text{odd}} = \text{odd} \end{align}

from the above argument we conclude that if $m = \text{odd}$ then $s = \text{odd}$ and thus $m - s$ and $m + s$ are both $\text{even}$, hence $\frac{m+s}{2}, \frac{m-s}{2} \in \mathbb{Z} \Longrightarrow u,v \in \mathbb{Z}$. By a similar argument, when $m = \text{even}$ we get that the parity of $s$ is

(13)
\begin{align} \sqrt{ (\text{even})^2 - \text{even} } = \sqrt{ \text{even} - \text{even} } = \sqrt{\text{even}} = \text{even} \end{align}

and thus $\frac{m+s}{2}, \frac{m-s}{2} \in \mathbb{Z} \Longrightarrow u,v \in \mathbb{Z}$. So we conclude that in both cases, $u$ and $v$ will always be integers. It can be readily seen that $m=u+v$ and $k=uv$. Now let's look at the signs (positive or negative) of $u$ and $v$. Since $k$ is positive, we get that $u$ and $v$ have the same sign. But since their sum (which is $m$) is also positive, then they can't be both negative, and thus $u$ and $v$ are both positive, or $u,v \in \mathbb{Z^+}$. Now we deduce that

(14)
\begin{align} n = m \cdot \frac{n}{m} = (u+v)(m^2 -3k) = (u+v)((u+v)^2 - 3uv) = (u+v)(u^2 - uv + v^2) = u^3 + v^3 \end{align}

and thus $n$ can be represented as a sum of two positive cubes. $\Box$

Germain Primes

Define: A prime $p$ is said to be a Sophie Germain prime if both $p$ and $2p+1$ are prime.

Examples: The first few Sophie Germain primes are $2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, ...$ It is not known if there are an infinite number of Sophie Germain primes.

The largest known Sophie Germain prime as of Feb. 2009 has $p= 48047305725 \cdot 2 ^{172403} - 1$, which has $51910$ decimal digits and was found by Chris Caldwell on Jan. 25, 2007.

Theorem: Let $p \equiv 3 \mod{4}$ be prime. $2p+1$ is also prime if and only if $2p+1$ divides $M_p$, a Mersenne number of the form $2^{p} - 1$.

Proof: $( \Longrightarrow )$ Suppose $q = 2p+1$ is prime. Then $q = 2p + 1 = 2 (4k+3) + 1 \;\; \text{[by how we defined p]} \; = 8k+7 \equiv 7 \mod{8}$ so $q \equiv 7 \mod{8}$ so $2$ is a quadratic residue $\text{mod} \; q$ and $\left( \frac{2}{q} \right) = 1$. This shows,

(15)
\begin{align} 2^{p} \equiv 2^{\frac{q-1}{2}} \equiv \left( \frac{2}{q} \right) \; \; \text{[by Euler's Criterion]} \; \equiv 1 \mod{q} \Longrightarrow q \mid M_p \end{align}

$( \Longleftarrow )$ Conversely, let $2p+1$ be a factor of $Mp = 2^{p} -1$. So $2p+1 \mid 2^{p} -1$. We want $2p+1$ to be prime. For contradiction, suppose $2p+1$ is composite and let $m$ be its least prime divisor, which implies $2p+1 \ge m^2$. This is because the prime factorization of $2p+1$ must include at least one other prime divisor, call it $d$. So we get that $2p+1 \ge m\cdot d$ but $d \ge m$ because $m$ is the least prime divisor of $2p+1$, so we get that $2p+1 \ge m \cdot d \ge m \cdot m = m^2$. Now we get,

(16)
\begin{align} m \mid 2p+1 \;\; \text{and} \; \; 2p+1 \mid 2^{p} -1 \Longrightarrow m \mid 2^{p} -1 \Longrightarrow 2^{p} \equiv 1 \mod{m} \Longrightarrow \text{ord}_m(2) \mid p \end{align}

Now, $p$ is prime, so its only divisors are $1$ and $p$, which means $\text{ord}_m(2) = 1 \; \text{or} \; p$. If $\text{ord}_m(2)= 1$, then $2^{1} \equiv 1 \mod{m} \Leftrightarrow m \mid 2-1 \Leftrightarrow m \mid 1$, which can't happen. So $\text{ord}_m(2) = p$.

Since $m$ is prime, Fermat's little theorem gives $2^{m-1} \equiv 1 \mod{m} \Longrightarrow \text{ord}_m(2) \mid m-1$, but $\text{ord}_m(2) = p$ so $p \mid m-1 \Longrightarrow m > p \Longrightarrow m^{2} > p^{2}$. We know $2p+1 \ge m^{2}$, so $2p+1 \ge m^2 > p^2 \Longrightarrow 2p+1 > p^2$. However, since $p>2$, this is a contradiction, so $2p+1$ is prime. $\Box$

Perfect Numbers

Euclid gave in Book IX of the Elements a very wordy description of perfect numbers as seen below:

"If as many numbers as we please beginning from a unit are set out continuously in double proportion until the sum of all becomes prime, and if the sum multiplied into the last makes some number, then the product is perfect."

Which roughly translates to: $\text{if } \;\; 1+2+2^{2}+...+2^{k} \;\; \text{ is prime, then that sum times } \;\; 2^{k} \;\; \text{ must be perfect}$.

Examples:

(17)
\begin{align} 1+2=3 \;\; \Longrightarrow 3 \cdot 2=6 \;\; \text{ is perfect and } \;\; 1+2+2^{2}=7 \;\; \Longrightarrow7 \cdot 2^{2}=28 \;\; \text{is perfect} \end{align}

We then listed the first four perfect numbers: 6, 28, 496, and 8128 which led to Nicomachus five unproven claims of perfect numbers:

1. The $n^{th}$ perfect number has $n$ digits.
2. All perfect numbers are even.
3. All perfect numbers end in either $6$ or $8$, alternately.
4. Euclid's Algorithm to generate perfect numbers will give all perfect numbers. $2^{p-1} \cdot (2^{p} - 1) \;\; \text{for} \;\; p\ge 1 \;\; \text{ and } \;\; (2^{p} - 1) \;\; \text{ prime}$. Euler later proved this was only the case when $p$ was prime.
5. There are infinitely many perfect numbers.

Claim 4 if we remember, was proven by Andy in lecture 15. Click here for a refresher Lecture 15 - Perfect Numbers. Thus we were able to check this claim as being true.

Claim 2 is believed to be true as no odd perfect numbers have yet to be found. Many are trying to prove the existence of odd perfect numbers and have a lower bound of $10^{300}$. However many are also trying to prove the non existence of odd perfect numbers. Check out the links below if interested to learn more about odd perfect numbers.

A site listing requirements of Odd Perfect Numbers.
Carl Pomerance's Heuristic approach to Disproving Odd Perfect Numbers

Claim 5 is also accepted to be true but still unproven since the number of Mersenne primes is still unknown and since whenever you find a new Mersenne prime, you also find an even perfect number, and vice versa.

Disproving Claim 1
Having Euclid's Algorithm, Haldrichus Regins in 1536 was able to show $(2^{11} - 1) = 2047 =23 \cdot 89$ which is not a Mersenne prime and thus not leading to a perfect number. By then testing $(2^{13} - 1) =8191$ he was able to show it was prime and thus resulting in the fifth perfect number: $2^{12} \cdot (2^{13} -1) = 33,550,336$. He was able to show that $8191$ is prime by taking the square root of $8191$ and then testing whether any of the primes below that value were able to divide $8191$.
As we can see, the fifth perfect number here has $n=8$ digits and thus disproves claim 1 listed above.

Claim 3
In a similar fashion as Regins, Cataldi in 1603 constructed two tables. The first was a table of the numbers $1$ through $800$ and all of the factors for each number. He was then able to construct a table with all the prime numbers between $1$ and $750$. Since $750^{2} = 562,500$ Cataldi knew that he had all prime divisors possible for $(2^{17} - 1) = 131,071 < 562,500 = 750^2$.
Through tedius calculations he was able to show that $131,071$ is prime, thus resulting in the sixth perfect number: $2^{16} \cdot (2^{17}-1) = 8,589,869,056$. However because the fifth and sixth perfect numbers both end in $6$, claim 3 is partially false. We know they don't alternate between $6$ and $8$, but do all perfect numbers end in $6$ or $8$? The proof proving this follows:

Theorem: Every perfect number ends in either $6$ or $8$.

Proof: Every prime number greater than $2$ is of the form $4m+1 \;\; \text{or} \;\; 4m+3$.

Case 1: $p=4m+1$. We will use this property: $6^m \equiv{6} \pmod{10} ; \forall \; m \in \mathbb{Z^+}$ which can be proven easily by induction: for $m=1$ we have $6^1 \equiv{6} \pmod{10}$, now suppose that $6^m \equiv{6} \pmod{10}$ for some integer $m \ge 2$, now notice that $6^{m+1} \equiv{6 \cdot 6^m} \equiv{ 6 \cdot 6} \equiv{36} \equiv{6} \pmod{10}$ so the statemnet holds for all integers $m \ge 1$. Now let $N$ be our perfect number

(18)
\begin{align} N=2^{4m} \cdot (2^{4m+1}-1) = 16^{m} \cdot (2 \cdot 16^{m}-1) \equiv 6^{m} \cdot (2 \cdot 6^{m}-1) \equiv 6 \cdot (2 \cdot 6 -1) \equiv{ 6 \cdot 11} \equiv{6} \pmod{10} \end{align}

Thus showing when a prime is of the form $4m+1$ and results in a Mersenne prime, the resulting perfect number will end in $6$.

Case 2: $p=4m+3$. Let $N$ be our perfect number

(19)
\begin{align} N=2^{4m+2}\cdot (2^{4m+3}-1) = 4 \cdot 16^{m} \cdot (8 \cdot 16^{m}-1) \equiv 4 \cdot 6 \cdot (8 \cdot 6-1) \equiv{24 \cdot 47} \equiv{ 4 \cdot 7 } \equiv{8} \pmod{10} \end{align}

Thus showing when a prime is of the form $4m+3$ and results in a Mersenne prime, the resulting perfect number will end in $8$.

Case 3: $p=2$. Let $N$ be our perfect number

(20)
\begin{align} N=2^{1} \cdot (2^{2}-1) = 2 \cdot 3 = 6 \end{align}

Since when our prime is $2$ our perfect number is $6$, we can conclude that all even perfect numbers end in $6$ or $8$ and thus claim 3 was partially true.$\Box$

To finish the presentation Tom presented a couple other facts about perfect numbers. First off at the moment there are 46 known even perfect numbers with the largest having 26 million digits! And secondly, the reciprocals of the divisors of a perfect number add up to 2.

Proof:
Let $N$ be our perfect number. We have $\sigma (N) = 2N$ . Let $\lbrace d_1 , d_2 , ... , d_k \rbrace$ be the set of positive divisors of $N$.

(21)
\begin{align} \frac{1}{d_1} + \frac{1}{d_2} + ...+ \frac{1}{d_{k-1}} + \frac{1}{d_k} \text{ has common denominator N, since all divisors divide evenly into N.} \end{align}

In addition if you divide $N$ by one of its divisors, you result in another divisor of $N$. Without loss of generality, let $1 = d_1 < d_2 < .... < d_{k-1} < d_k = N$. Now, since $N$ has an even number of divisors (because $N$ is of the form $2^{p-1} \cdot (2^p - 1)$ and this form has only one copy of the prime $2^p -1$ and thus $N$ can't be a perfect square, and only perfect squares have an odd number of divisors) then we have "divisor pairs" where $(d_1 \cdot d_k) = N , (d_2 \cdot d_{k-1}) = N, ....$ and so on for all divisors of $N$. Thus if we adjust for a common denominator in the summation of the reciprocals above we simply get

(22)
\begin{align} \frac{d_1 + d_2 +...+ d_{k-1} + d_k}{N} \Longrightarrow \frac{\sigma (N)}{N} = \frac{2N}{N} =2 \end{align}

$\Box$

Bibliography
1. Auburn, David. Proof. New York: Faber and Faber, Inc., 2001.
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License