# 1.1: What Is Number Theory?

- Page ID
- 93785

Welcome to number theory!

In this chapter we will see a bit of what number theory is about and why you might enjoy studying it. Carl Friedrich Gauss (1777–1855), one of the greatest mathematicians of all time, had this to say about number theory (which he called *arithmetic*):

Mathematics is the queen of sciences and arithmetic the queen of mathematics.

- Quoted by Sartorius von Waltershausen in Gauss zum Gedachtniss (1856)

So what is "arithmetic," or number theory?

Simply stated, number theory is concerned with questions about and properties of the integers \[\dots, -4, -3, -2, -1, 0, 1, 2, 3, 4, \dots\nonumber \] and closely-related numbers. Since you've been dealing with whole numbers of one kind or another for almost your whole life, some of what we'll see in the text will seem familiar, and much may seem simple and easy at first glance. Still, number theory is a surprisingly deep subject, and though this text only delves into what is known as *elementary number theory*, you will see new and different sides to a few things you may have thought you already knew.

## Whetting your appetite

To give you a taste of what number theory is like, look at the following three questions:

### Writing numbers as sums of squares

A *perfect square* is a number obtained by squaring an integer. For example, the four smallest perfect squares are \[0=0^2, \qquad 1 = 1^2 = (-1)^2, \qquad 4 = 2^2 = (-2)^2, \qquad 9 = 3^2 = (-3)^2.\nonumber \] A list of 21 perfect squares is found in Appendix B.

As you can see, not every integer is a perfect square, and in fact the perfect squares get farther apart the larger they get. However, more numbers can be made by adding perfect squares together, which is what this question is about.

Which numbers can be written as the sum of two perfect squares? If we try putting \(0, 1, 4, 9\) together in pairs (possibly taking two of the same number), we can create \(0,1,2,4,5,8,9,10,13,18\). As we use later squares to do the building, we see that the complete list of numbers that can be written as perfect squares begins with \[0, 1, 2, 4, 5, 8, 9, 10, 13, 16, 17, 18, 20, 25, 26, 29, 32, 34, 36, 37, 40, \dots.\nonumber \] Is there any pattern to which whole numbers do or do not appear in the list?

Similarly, which numbers can be written as the sum of three perfect squares? The list begins with \[0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20, 21, 22, 24, \dots.\nonumber \] It looks like most nonnegative whole numbers show up here, but 7, 15, and 23 do not. Is it a coincidence that these non-appearing numbers are 8 apart—would 31 be the next non-appearing number?

Which numbers can be written as the sum of four perfect squares? Allowing an extra square allows us to produce some numbers we couldn't before; for example, \(23 = 9 + 9 + 4 + 1\). Making a list of those numbers that can be written with four squares, we begin with \[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,\dots;\nonumber \] in fact, checking all numbers between 0 and 100 shows that *every one* can be written as a sum of 4 perfect squares. Is it true that every positive integer is the sum of four squares? If so, why is this?

### Finding a formula for prime numbers

You probably remember that a prime number is a number greater than 1 for which the only positive integers that evenly divide it are itself and 1. The first several prime numbers, beginning with \(2,3,5,7,11,13,\dots\), are listed in Appendix A.

As we will see in the text, understanding prime numbers is a very important part of understanding many of the properties of integers. Is there a nice way to generate prime numbers? Perhaps a formula?

Consider the function \(f(n) = n^3 + n^2 + 17\). Plugging in some integer values of \(n\), we find \[f(0)=17, \qquad f(1)=19, \qquad f(2) = 29, \quad \text{and} \quad f(3) = 53.\nonumber \] Each of these is prime, and in fact, plugging in each of the numbers from 0 to 10 always produces a prime number. Could \(f(n)\) be a prime number for all \(n\)? And are there other functions or techniques for producing prime numbers?

### Integer solutions to equations

Can you find a pair of integers \(x,y\) such that \(3x+17y = 10\)? A little trial and error might lead you to \(x=-8\) and \(y=2\), but is this the only pair of integers that works? And is there a way besides trial and error that can systematically produce one or all of the solutions?

Other equations, like \(154x - 33y = 10\), seem to have no solution where \(x\) and \(y\) are both integers. Why is this, and can we recognize equations like this from patterns in the numbers involved?

What about just slightly more complicated equations, like \(x^2 + 3y = 1\)? Why does this have several solutions in the integers (like \(x=1,y=0\), and \(x=2,y=-1\), and \(x=4,y=-5\)), while \(x^2 + 3y = 2\) seems to have none?

Here's a famous equation along the same lines: Can you find positive integers \(x,y,z,n\) with \(n\) greater than 2 such that \(x^n + y^n = z^n\)?

We'll touch at least briefly on each of these questions throughout the text. Specifically:

- Clues about the answers to the sums-of-squares questions will be answered in a few places, culminating in a complete answer in Section 1.28.
- Prime numbers will be studied in depth in Sections 1.11, 1.14, 1.24, and 1.25, and one example of a valid prime-generating formula will be presented in the exercises of Section 1.24. Incidentally, the function \(f(n)\) above cannot always generate prime numbers—what happens if \(n=17\)?
- The keys to finding integer solutions to linear equations with integer constants will be developed in the text and exercises of Sections 1.8, 1.9, and 1.10. We will not be able to present solution techniques to some of the more complicated equations mentioned above, but with a little library work or searching online, you will be able to find out and, perhaps with a little patience and effort, digest and appreciate what's been solved. (You might start by doing a little reading on Fermat's Last Theorem.)

## A practical application

In addition to answering these theoretical curiosities, we'll develop the tools used in the RSA cryptosystem, a widely used modern scheme for encrypting sensitive digital information.

As a simplified example, an online seller might publicly instruct a web browser using RSA to encrypt part of a credit card number, say, the number '1234' (perhaps part of a credit card number) by raising it to the exponent \(43\) and finding the remainder when the answer is divided by \(1517\). (We abbreviate the "find the remainder after dividing by" instruction by "mod".) The browser computes \[1234^{43} \bmod 1517 = 1253\nonumber \] and, instead of transmitting the sensitive number '1234', transmits the encrypted number '1253.' The online seller then uses a secret decryption exponent (67) and the same "remainder process" to change the encrypted message back into the original: \[1253^{67} \bmod 1517= 1234.\nonumber \] So how does this work? How are the numbers 1517, 43, and 67 chosen? And how do we find division's remainders when the exponents involved produce such large numbers?\(^{1}\) These questions are answered in Sections 1.26 and 1.27, using results developed all throughout the text. As we will see, the strengths of the RSA system (and the codebreaking attacks that can break it if the numbers are not chosen wisely) have everything to do with the number theoretic properties of the numbers used to do the encryption and decryption.

## The themes

The questions and application above illustrate some themes we'll run into throughout the text. We will look at various forms in which integers can sometimes be written. We will look multiple times at producing or identifying prime numbers. We will look for integer solutions to equations, and we will use properties of the integers to design algorithms to accomplish many different tasks. As you skim the table of contents now, and perhaps return to this chapter occasionally as you go through the text, you'll see these themes (and others) played out again and again.

There's another happy feature of number theory: many of the results we'll discuss won't be necessarily hard to recognize when you see them in action—in fact, several of the results will pop up quite easily as we look for patterns among multiple examples. (Of course, as mathematicians we're never satisfied until we can rigorously justify our observations through proof, but I hope you'll find the proofs in this text pleasant to digest, as well.)

Because number theory is about patterns in the integers, you will be well served to work out several numerical examples of ideas you encounter in the text and exercises. If you are familiar with writing simple programs in a computer algebra system (eg., CoCalc, Maple, Mathematica, MATLAB) or in a programming language, please try often to turn what you see in your studies into programs. You will be able to see many more examples this way, and the thought processes involved in writing your programs will enhance your understanding of number theory. As contemporary number theorist William Stein has said,

A computer is to a number theorist, like a telescope is to an astronomer. It would be a shame to teach an astronomy class without touching a telescope; likewise, it would be a shame to teach this class without telling you how to look at the integers through the lens of a computer.

Because there is a wide variety in the programming/computing environments with which students may be familiar, this book will not focus on any one computational system; however, you are heartily encouraged to pick one and dig deeply into number theory with it.

## Three wishes

This book will have succeeded if it helps you do the following (not necessarily in order of importance):

- appreciate the beauty of patterns found in the integers;
- appreciate some of the practical applications of number theory;
- continue your growth in mathematical maturity and skill.

Here's to our success...Let's get started!

## Footnotes

[1] The number \(1253^{67}\) has \(208\) digits, and the numbers used in this example are much

smaller than those used in practice!