My goal in this post is to describe a surprising and beautiful method (the Stern-Brocot tree) for generating all positive reduced fractions. I’ll then discuss how properties of the tree yield a simple, direct proof of a famous result in Diophantine approximation due to Hurwitz. Finally, I’ll discuss how improvements to Hurwitz’s theorem led Markoff to define another tree with some mysterious (and partly conjectural) similarities to the Stern-Brocot tree.
Category Archives: Elementary number theory
p-adic Numbers and Dissections of Squares into Triangles
My thesis advisor Robert Coleman passed away two years ago today (see this remembrance on my blog). One of the things I learned from Robert is that p-adic numbers have many unexpected applications (see, for example, this blog post). Today I want to share one of my favorite surprising applications of p-adic numbers, to a simple problem in Euclidean geometry. Continue reading
Probability, Primes, and Pi
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 
Number Theory and Cryptography: A Distance Learning Course for High School Students
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.
Continue reading
The Sign of the Quadratic Gauss Sum and Quadratic Reciprocity
Today marks the birthday of Karl Friedrich Gauss
, the “Prince of Mathematicians”, who was born on April 30, 1777. In honor of Gauss’s 238th birthday, I thought I would blog about one of Gauss’s favorite theorems — the Law of Quadratic Reciprocity — and its relation to the sign of the quadratic Gauss sum, which we will determine using the Discrete Fourier Transform. Our exposition mostly follows this paper by Ram Murty. Regarding the sign of the quadratic Gauss sum, Gauss conjectured the correct answer in his diary in May 1801, but it took more than four years until he was able to find a proof in August 1805. Gauss wrote to his friend W. Olbers that seldom had a week passed for four years that he had not tried in vain to prove his conjecture. Then:
Finally, two days ago, I succeeded – not on account of my hard efforts, but by the grace of the Lord. Like a sudden flash of lightning, the riddle was solved. I am unable to say what was the conducting thread that connected what I previously knew with what made my success possible.
Post-Cherylmania wrap-up
My last post was about “Cheryl’s birthday puzzle”, which recently became an internet sensation. I mentioned several additional puzzles in that post and promised solutions; here they are.
Let me begin, though, with a “cryptography” variant of the Cheryl puzzle which was sent to me by my friend and puzzle guru Pete Winkler:
Cheryl’s birthday possibilities are now May 14 or 15, June 15 or 16, July 16 or 17 or August 14 or 17. Albert gets the month and Bernard the day as before, and they both want to find out the birthday. But Eve, who’s listening in, mustn’t find out. How can A and B, who’ve never met before (and aren’t cryptographers), accomplish this mission?
Think about it, it’s a fun little puzzle! [Pete writes in addition: “You can also do this with a cycle of 5 months (10 dates total) but then you need a coin to flip.”]
My Meta-Cheryl Challenge (as revised on April 20) was to come up with a list of dates for which the following puzzle will have a unique solution:
A motivated and simple proof that pi is irrational
Today is 3/14/15 — Super Pi Day — so was I telling my 7-year-old son all about the number
Newton polygons and Galois groups
Issai Schur
A famous result of David Hilbert asserts that there exist irreducible polynomials of every degree 
In this post, we give a simple proof of Schur’s result using the theory of Newton polygons. The ideas behind this proof are due to Robert Coleman and are taken from his elegant paper On the Galois Groups of the Exponential Taylor Polynomials. (Thanks to Farshid Hajir for pointing out to me that Coleman’s method applies equally well to the Laguerre polynomials.) Before we begin, here is a quote from Ken Ribet taken from the comments section of this post:
Lucas sequences and Chebyshev polynomials
This is a sequel to last week’s blog post “Two applications of finite fields to computational number theory“. The main reason I decided to write a follow-up is that I’ve learned a lot about Concluding Observations #1 and #6 from that post during the last week. 
In Observation #1, I mentioned without further comment a recursive procedure for computing square roots modulo a prime; it turns out that this procedure is essentially equivalent to Cipolla’s algorithm, but was discovered independently by Lehmer (who it seems did not know about Cipolla’s work). I learned this from the wonderful book “Édouard Lucas and Primality Testing” by Hugh C. Williams, which I highly recommend to anyone interested in the history of mathematics. In explaining the connection between the algorithms of Cipolla and Lehmer, I’ll make a digression into the general theory of Lucas sequences, which I had some vague knowledge of before but which I’ve learned a lot about in the last week from reading Williams’ book. In Observation #6, I asked if there was a conceptual explanation for the fact that the Chebyshev polynomial 
Two applications of finite fields to computational number theory
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.
Anecdotal Prelude
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 
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
Primitive roots, discrete logarithms, and p-adic numbers
This morning I attended Martin Hellman’s stimulating keynote address at the 2013 Georgia Tech Cyber Security Summit. Martin Hellman is the co-inventor, with Whitfield Diffie, of the Diffie-Hellman Key Exchange Protocol, which began the (public) public-key cryptography revolution. Among the interesting things I learned during Martin Hellman’s talk are:
1. Hellman feels that Ralph Merkle deserves equal credit for inventing public-key cryptography and refers to his own invention as the Diffie-Hellman-Merkle key exchange protocol. (Merkle was the director of the Georgia Tech Information Security Center from 2003-2006.)
2. Hellman came up with the famous “double padlock” thought experiment after the invention of the Diffie-Hellman-Merkle key exchange protocol, as a way to explain it to others. The mathematics came first. (I had always wondered about this.)
3. Most interestingly, Hellman said that he got the idea to use modular exponentiation/discrete logarithms as a “one-way function” from the engineer and mathematician John Gill (who I never heard of before this morning). John Gill’s other suggestion was to use multiplication/factoring, which forms the basis of RSA! It’s all the more amazing that I’ve never heard of John Gill because he earned his bachelor’s degree in Applied Mathematics from Georgia Tech (where I now teach) and his Ph.D. in Mathematics from U.C. Berkeley (where I got my Ph.D.)! Hellman also recounted a conversation in which Gill (who is African-American) mentioned having encountered very little racial intolerance during his undergraduate studies in the 1960’s — apparently Georgia Tech was (relatively speaking) an oasis of tolerance among southern universities during that time.
Now on to the mathematical part of this post, which is an unusual proof of the existence of primitive roots modulo primes which I came up with recently while preparing a lecture for my course on Number Theory and Cryptography. The proof is much less elementary than every other proof I’ve seen, but I would argue that it nevertheless has some merit. Continue reading
Quadratic reciprocity and Zolotarev’s Lemma
I want to explain a beautiful proof of the Law of Quadratic Reciprocity from c. 1874 due to Egor Ivanovich Zolotarev (1847-1878). Some time ago I reformulated Zolotarev’s argument (as presented here) in terms of dealing cards and I posted a little note about it on my web page. After reading my write-up (which was unfortunately opaque in a couple of spots), Jerry Shurman was inspired to rework the argument and he came up with this elegant formulation which I think may be a “proof from the book”. The following exposition is my own take on Jerry’s argument. The proof requires some basic facts about permutations, all of which are proved in this handout.
Let 
Row deal (
