Author: Delta

  Note: “introductory methods” here means techniques used in an introductory treatment of elementary number theory, not advice on how to begin studying the subject. I am clarifying the distinction up front to avoid ambiguity.

  Before we begin, let me ask a question:

  Is √2 an integer?

  There are only two possible answers: yes or no. Most readers will probably say no, because √2 is an ordinary irrational number, whereas the integers are 0, ±1, ±2, and so on. What comes next, however, may upend that assumption.

  √2 really is an integer.

  To see why, we first need the definition of an algebraic number:

  Every rational number, and every irrational number that can be expressed in radicals, is algebraic: each is a root of some polynomial with rational coefficients. An algebraic integer must meet a stricter condition:

  The equation x²-2=0 satisfies the required polynomial conditions, so its root √2 is an algebraic integer, or simply an “integer” in this context. Algebraic integers generalize the rational integers 0, ±1, ±2, and so on. They include every rational integer, but no nonintegral rational number—that is, no reduced fraction whose denominator is not 1.

  Now back to √2. Why would mathematicians introduce a definition that calls it an integer? This is the viewpoint of algebraic number theory, a field developed largely in pursuit of Fermat’s Last Theorem. More generally, solving problems about Diophantine equations requires extending number-theoretic properties of the ring of integers to broader classes of integral domains. That need gave rise to algebraic number theory, which studies such domains through their algebraic structure.

  (Audience: Stop, stop, stop! Why do you keep throwing more unfamiliar terms at us?)

  All right. Let me explain them one at a time:

  Algebraic number theory is only one branch of number theory, developed to address problems that arose in pure mathematics. It cannot solve every problem in number theory, so the field has grown many other branches, including analytic, computational, geometric, transcendental, and combinatorial number theory. In short, a particular problem calls for the right mathematical tools and, when necessary, broader definitions. This is standard practice in mathematics:

  If a definition is too narrow, generalize it. If the generalization still fails to provide the properties you need, revise it. If that does not work either, discard it.

  Our real subject today is the simplest branch of number theory: elementary number theory, which deals mainly with positive integers and their properties. I brought up algebraic number theory only to catch your attention, since its use of the word “integer” overturns many people’s expectations. There is no real contradiction, only a change in terminology. If you said √2 was not an integer, you were entirely right: you meant the integers of elementary number theory, the ones you have studied for more than a decade, not the algebraic integers of algebraic number theory. I simply switched meanings on you.

  Now we can begin the actual introduction to elementary number theory. From this point on, every term has its familiar elementary-number-theory meaning.

  We will begin again with our protagonist, √2. Here is another question: Is √2 rational?

  Of course not! The last question may have made some readers wary, but first I need to clear up a common misconception:

  We usually call a number of the form p/q a “fraction.” The reduced fraction mentioned earlier is a particular kind of fraction, used so that the set of rational numbers does not contain duplicate representations. What exactly is a reduced fraction? Before wading into the formal definition, let us look at a few examples:

  You have probably spotted the difference already. In primary school, we learned to reduce fractions. A fraction that has not been reduced completely is not in lowest terms. That makes the idea fairly easy to understand, doesn’t it?

  We also learned the next two ideas in primary school: the greatest common divisor (gcd) and least common multiple (lcm). Two numbers are coprime, or relatively prime, if their greatest common divisor is 1. If they are not coprime, the fraction formed from them is not in lowest terms. For brevity, we will write the greatest common divisor of a and b as (a,b), and their least common multiple as [a,b].

  With that background in place, we can prove that √2 is irrational.

  Similar arguments work for other radicals. To digress briefly into algebraic number theory once more, this method can establish the irrationality of every irrational algebraic number. In other words, these numbers share a common property that elementary number theory treats case by case. That is one reason a separate field, algebraic number theory, became necessary.

  All right, back to elementary number theory. With what we now know, plus Vieta’s formulas for quadratic equations that we learned in middle school, we already know enough to enter the IMO and win a bronze medal—at least at the 1988 IMO:

  Here is the proof:

  The part about “winning an IMO bronze medal” was only a joke. In fact, if I had not shown you this solution, you might spend your entire life without finding it. Why? Is the problem really that hard?

  Terence Tao earned only two points on this problem. Experts from the entire Olympiad committee, along with four Australian number theorists, worked for 4.5 hours without making meaningful progress. So as we explore the mathematics, I would also advise against showing off after learning only a little. All of us, myself included, may still lack the experience to judge our own ability or to know whether we truly understand the deeper ideas. A little humility goes a long way.

  What matters is the central idea. In the proof, we assume a minimum and then construct something smaller, creating a contradiction. Number theorists call this method infinite descent, and they commonly use it to solve Diophantine equations. When infinite descent is combined with Vieta’s formulas as it is here, the technique is called Vieta jumping.

  Infinite descent is useful for more than solving Diophantine equations. It can also prove that √2 is irrational. The argument is quite simple, so try working it out for yourself before consulting the version from Baidu below—I was too lazy to type it out:

  As we can see, this is a powerful form of proof by contradiction. There is also a corresponding method called infinite ascent, though ascent and descent are essentially the same idea. With an infinite-ascent argument, we can prove the following fact:

  There are infinitely many primes.

  Of course not. Believe it or not, this probability is connected to pi!

  (Audience: ??? Doesn’t elementary number theory deal mainly with positive integers? At most, shouldn’t it bring in a few rational numbers? How did pi get involved?)

  (An audience member who knows some algebraic number theory: Exactly! Even algebraic number theory deals with algebraic numbers, while pi is transcendental. How could they possibly be related?)

  The story begins 400 years ago. Legend has it that Wu Cheng’en dreamed of Sun Wukong wreaking havoc in heaven, woke up, and wrote Journey to the West… Ahem, wrong script. It was not more than 400 years ago, but almost 400: 376 years, to be exact.

  In 1644, Pietro Mengoli posed a famous problem about an infinite series:

  The problem stumped mathematicians for 91 years before Leonhard Euler solved it in 1735. Named for Basel, Switzerland’s third-largest city and Euler’s hometown, it became known as the Basel problem.

  Today, the Basel problem is considered elementary and fairly simple. Anyone with a command of advanced mathematics can give a nonrigorous derivation. Euler presented such a derivation in 1735, then supplied a rigorous version in 1741.

  To explain Euler’s method, we begin with the Maclaurin series expansion:

  A Fourier-series proof of the Basel problem follows directly from Parseval’s identity.

  Next, consider:

  and apply a few simple manipulations.

  To keep the expression concise and readable, we omit the limit notation and write:

  Then:

  This gives us the exact sum of the reciprocal squares of all even positive integers.

  Now subtract the second equation from the first:

  This gives us the exact sum of the reciprocal squares of all odd positive integers as well.

  Put another way, summing over all odd numbers is the same as summing over the positive integers after removing every multiple of 2. Could we repeat the process, removing the multiples of 3 that are not already multiples of 2, then the multiples of 5 that are not multiples of 2 or 3, and so on until every composite number is gone?

  Let us carry out that process:

  Then:

  We also have:

  Repeating the procedure yields the equation below, where p ranges over all primes:

  This proof shows how closely the branches of mathematics are connected. You might begin with number theory and soon find yourself working in calculus or complex analysis. Push the argument above a little further, and it leads to the Riemann hypothesis.

  Now set aside the probability that two randomly chosen positive integers are coprime, and consider a simpler problem:

  Choose n+1 numbers from the positive integers less than 2n. What is the probability that at least two of them are coprime?

  One hundred percent.

  (Audience: That’s it, we’re leaving. You’re messing with us. Didn’t you just say the answer involved pi?)

  For unrestricted positive integers, it does involve pi. But the new constraints make this problem much simpler. Once we know the pigeonhole principle, the solution is easy.

  The pigeonhole principle:

  If more than n+1 objects are placed in n pigeonholes, at least one pigeonhole contains at least two objects.

  The principle itself is intuitive, and I am sure everyone understands it. The hard part is deciding what the pigeonholes should be. Let us see how Louis Pósa answered this problem when he first encountered it, before he was twelve:

  What a clever construction! But why must consecutive positive integers be coprime? Before moving on, try a few examples. You will notice that consecutive integers can never share a common factor. In fact, we have:

  How does Bézout’s identity show that consecutive positive integers are always coprime? Set x=1 and y=-1, and the result follows immediately.

  That brings us close to the end of this introduction. Looking back, we have spent most of our time on properties of positive integers: coprimality, divisibility, least common multiples, and greatest common divisors. Positive integers alone give rise to many intricate and beautiful theories, and some of their questions remain unsolved. Consider Goldbach’s conjecture. On June 7, 1742, Christian Goldbach, a Prussian envoy to Russia, wrote to Euler and proposed that “every even number beginning with 4—that is, every large even number—can be expressed as the sum of two primes; every odd number beginning with 7 can be expressed as the sum of three primes. The latter follows from the former and can also be proved independently (it has now been solved).” Later mathematicians adopted a compact notation: expressing a large even number as the sum of a product of at most a primes and a product of at most b primes is called the (a+b) problem. Chen Jingrun’s result, the closest step toward Goldbach’s conjecture, expresses a large even number as the sum of a prime and a product of at most two primes. It is therefore written (1+2), not 1+2=3. Likewise, Goldbach’s conjecture expresses a large even number as the sum of one prime and another prime, so it is written (1+1), not 1+1=2. If the generations of mathematicians worn out by Goldbach’s conjecture knew how many people now repeat the claim that “1+1=2 has not been proved,” they might rise from the dead in fury.

  That covers everything planned for this introduction. Until fate brings us together again~