A few years ago I discovered an amusing proof of Euclid’s theorem that there are infinitely many primes which I thought I’d record here for posterity. (I subsequently learned that a similar argument appears in this paper by Paul Pollack.)
To motivate the proof, and illustrate its working in an (admittedly silly) special case, suppose that there were just two prime numbers, called p and q. Then by the fundamental theorem of arithmetic (i.e., unique factorization into primes) we would have the following identity between generating functions:
Indeed, there is precisely one term for each integer on the left-hand side, and the same is true for the right-hand side (consider separately the cases where but , but , and ). Using the formula for the sum of a geometric series, we can rewrite our formula as an identity between complex-analytic functions valid on the open unit disc :
This is impossible, however, as we see by letting approach a primitive root of unity, since each term stays bounded except for , which tends to infinity.
What is the probability that two randomly chosen integers have no prime factors in common? In honor of Pi Day, I’d like to explain the surprising answer: .
The hero of this story is Leonhard Euler, who worked out this astonishing connection between prime numbers and through a series of brilliant insights. In the spirit of Euler, I will be rather cavalier about issues of convergence and rigor here, focusing on the key underlying ideas.
In my current position as Director of Undergraduate Studies for the Georgia Tech School of Mathematics, I’ve been heavily involved with revamping our linear algebra curriculum. So I’ve spent a lot of time lately reading through various linear algebra books. The goal of this post is to give a self-contained proof of the existence and uniqueness of the Jordan Canonical Form which is somewhat different from the ‘usual’ proofs one finds in textbooks. I’m not claiming any novelty — I’m sure this approach has been discovered before — but I don’t know a good reference so I thought I’d record the details here.
The proof I give here does not use properties of polynomials (e.g. the Chinese Remainder Theorem), nor does it rely on the classification of finitely generated modules over a PID, so it might be of some pedagogical interest. The proof I give for the Generalized Eigenvector Decomposition is based on an auxiliary result — the Fitting Decomposition — which in my opinion ought to be better known. The proof I give of the structure theorem for nilpotent operators comes from these lecture notes of Curt McMullen (Theorem 5.19). It is particularly concise compared to some other arguments I’ve seen. Continue reading
The following post was originally published on the AMS Blog “On Teaching and Learning Mathematics”. I have reproduced it here with the permission of the AMS.
Last year, I began offering an online Number Theory and Cryptography course for gifted high school students through Georgia Tech. Fourteen high school seniors from metro Atlanta took the course in Fall 2014, and overall I would say it was a big success. We will be offering the course again in Fall 2015 and are expecting roughly double the number of students. After describing the structure of the course, I will relate some of my experiences and describe some of the things I learned along the way. I hope this article stimulates others to think outside the box about using technology in education without necessarily following the standard “MOOC” model.
Many of you have undoubtedly heard by now the math puzzle about Cheryl’s birthday which has been sweeping across the internet. I appeared on CNN on Wednesday to explain the solution — here is a link to the problem and my explanation. Since that appearance, I’ve received dozens of emails about the problem and/or my explanation of it. I thought I’d share a few of my thoughts following this flurry of activity. Continue reading
Today is 3/14/15 — Super Pi Day — so was I telling my 7-year-old son all about the number this afternoon. When I told him that keeps on going forever and ever he asked “How do you know that?” Although I don’t know a proof that I could explain to a 7-year-old, I wanted to record the following proof which uses only basic calculus. It is essentially Niven’s famous proof, as generalized by Alan Parks, but I have tried to write it in a way which is more motivated than the usual treatments. As a bonus, the proof also shows that e is irrational.
In this post I’d like to illustrate how one can use infinite games to prove theorems about the real numbers. I’ll begin with a game-theoretic proof that the set of real numbers is uncountable, following the exposition in this paper of mine. This will lead us somewhat unexpectedly into the realm of descriptive set theory, where we will discuss how games are used in cutting-edge explorations of the Axiom of Choice, the Continuum Hypothesis, and the foundations of second-order arithmetic. In a sequel post I will discuss how infinite games can be used to study Diophantine approximation, with applications to complex dynamics.
Countable versus uncountable infinities
When my daughter was 5 years old, she asked me if there is just one infinity. I proudly kissed her on the forehead and told her what an excellent question that was. I told her no, infinity comes in many different flavors. I pretty much left it at that, but since she’s 10 now, here are some more details for her. (The reader familiar with the basics of set theory can move on to the next section.) Continue reading
I just moved into a new house and haven’t had time to blog much lately. But I did want to advertise my friend Manya Raman-Sundström’s upcoming Workshop on Beauty and Explanation in Mathematics at Umeå University in Sweden: http://mathbeauty.wordpress.com/wbem/
The list of invited speakers includes Hendrik Lenstra, one of my graduate school teachers. (If you haven’t see it before, you should check out Lenstra’s lovely short article Profinite Fibonacci Numbers.) Continue reading
In this post I’d like to discuss how finite fields (and more generally finite rings) can be used to study two fundamental computational problems in number theory: computing square roots modulo a prime and proving primality for Mersenne numbers. The corresponding algorithms (Cipolla’s algorithm and the Lucas-Lehmer test) are often omitted from undergraduate-level number theory courses because they appear, at first glance, to be relatively sophisticated. This is a shame because these algorithms are really marvelous — not to mention useful — and I think they’re more accessible than most people realize. I’ll attempt to describe these two algorithms assuming only a standard first-semester course in elementary number theory and familiarity with complex numbers, without assuming any background in abstract algebra. These algorithms could also be used in a first-semester abstract algebra course to help motivate the practical utility of concepts like rings and fields.
In researching this blog post on Wikipedia, I learned a couple of interesting historical tidbits that I’d like to share before getting on with the math.
The French mathematician Edouard Lucas (of Lucas sequence fame) showed in 1876 that the 39-digit Mersenne number is prime. This stood for 75 years as the largest known prime. Lucas also invented (or at least popularized) the Tower of Hanoi puzzle and published the first description of the Dots and Boxes game. He died in quite an unusual way: apparently a waiter at a banquet dropped what he was carrying and a piece of broken plate cut Lucas on the cheek. Lucas developed a severe skin inflammation and died a few days later at age 47.
Derrick Henry Lehmer was a long-time professor of mathematics at U.C. Berkeley. In 1950, Lehmer was one of 31 University of California faculty members fired for refusing to sign a loyalty oath during the McCarthy era. In 1952, the California Supreme Court declared the oath unconstitutional, and Lehmer returned to Berkeley shortly thereafter. Lehmer also built a number of fascinating mechanical sieve machines designed to factor large numbers. Continue reading