Introduction to Number Theory

We have used the natural numbers to solve problems. This was the right set of numbers to work with in discrete mathematics because we always dealt with a whole number of things. The natural numbers have been a tool. Let's take a moment now to inspect that tool. What mathematical discoveries can we make about the natural numbers themselves?

This is the main question of number theory: a huge, ancient, complex, and above all, beautiful branch of mathematics. Historically, number theory was known as the Queen of Mathematics and was very much a branch of pure mathematics, studied for its own sake instead of as a means to understanding real-world applications. This has changed in recent years however, as applications of number theory have been unearthed. Probably the most well-known example of this is RSA cryptography, one of the methods used to encrypt data on the internet. It is number theory that makes this possible.

What sorts of questions belong to the realm of number theory? Here is a motivating example. Recall in our study of induction, we asked:

Which amounts of postage can be made exactly using just 5-cent and 8-cent stamps?

We were able to prove that any amount greater than 27 cents could be made. You might wonder what would happen if we changed the denomination of the stamps. What if we instead had 4- and 9-cent stamps? Would there be some amount after which all amounts would be possible? Well, again, we could replace two 4-cent stamps with a 9-cent stamp, or three 9-cent stamps with seven 4-cent stamps. In each case we can create one more cent of postage. Using this as the inductive case would allow us to prove that any amount of postage greater than 23 cents can be made.

What if we had 2-cent and 4-cent stamps. Here it looks less promising. If we take some number of 2-cent stamps and some number of 4-cent stamps, what can we say about the total? Could it ever be odd? Doesn't look like it.

Why does 5 and 8 work, 4 and 9 work, but 2 and 4 not work? What is it about these numbers? If I gave you a pair of numbers, could you tell me right away if they would work or not? We will answer these questions, and more, after first investigating some simpler properties of numbers themselves.

It is easy to add and multiply natural numbers. If we extend our focus to all integers, then subtraction is also easy (we need the negative numbers, so we can subtract any number from any other number, even larger from smaller). Division is the first operation that presents a challenge. If we wanted to extend our set of numbers so any division would be possible (maybe excluding division by 0), we would need to look at the rational numbers (the set of all numbers that can be written as fractions). This would be going too far, so we will refuse this option.

In fact, it is a good thing that not every number can be divided by other numbers. This helps us understand the structure of the natural numbers and opens the door to many interesting questions and applications.

If given numbers \(a\) and \(b\), it is possible that \(a \div b\) gives a whole number. In this case, we say that \(b\) divides \(a\); in symbols, we write \(b \mid a\). If this holds, then \(b\) is a divisor or factor of \(a\), and \(a\) is a multiple of \(b\). In other words, if \(b \mid a\), then \(a = bk\) for some integer \(k\) (this is saying \(a\) is some multiple of \(b\)).

Given integers \(m\) and \(n\), we say \(m\) divides \(n\) and write \[m \mid n\] provided \(n \div m\) is an integer. Thus the following assertions mean the same thing:

1. \(m \mid n\)
2. \(n = mk\)\(k\)
3. \(m\)\(n\)
4. \(n\)\(m\)

Notice that \(m \mid n\) is a statement. It is either true or false. On the other hand, \(n \div m\) or \(n/m\) is some number. If we want to claim that \(n/m\) is not an integer, so \(m\) does not divide \(n\), then we can write \(m \nmid n\).

This last example raises a question: How might one decide whether \(m \mid n\)? Of course, if you had a trusted calculator, you could ask it for the value of \(n \div m\). If it spits out anything other than an integer, you know \(m \nmid n\). This seems a little like cheating though: We don't have division, so should we really use division to check divisibility?

While we don't really know how to divide, we do know how to multiply. We might try multiplying \(m\) by larger and larger numbers until we get close to \(n\). How close? Well, we want to be sure that if we multiply \(m\) by the next larger integer, we go over \(n\).

For example, let's try this to decide whether \(1642 \mid 136299\). Start finding multiples of 1642: \[1642 \cdot 2 = 3284 \qquad 1642 \cdot 3 = 4926 \qquad 1642\cdot 4 = 6568 \qquad \cdots\].

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

The division algorithm tells us that there are only \(b\) possible remainders when dividing by \(b\). If we fix this divisor, we can group integers by the remainder. Each group is called a remainder class modulo \(b\) (or sometimes residue class).

Note that in the example above, every integer is in exactly one remainder class. The technical way to say this is that the remainder classes modulo \(b\) form a partition of the integers. It is possible to develop a mathematical theory of partitions, prove statements about all partitions in general, and then apply those observations to our case here. The most important fact about partitions is that it is possible to define an equivalence relation from a partition: This is a relationship between pairs of numbers which acts in all the important ways like the equals relationship. Again, there is a mathematical theory of equivalence relations which applies in many more instances than the one we look at here. See .

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

We said earlier that congruence modulo \(n\) behaves, in many important ways, the same way equality does. Specifically, we could prove that congruence modulo \(n\) is an equivalence relation, which would require checking the following three facts:

Given any integers \(a\), \(b\), and \(c\), and any positive integer \(n\), the following hold:

1. \(a \equiv a \pmod{n}\)

2. If \(a \equiv b \pmod{n}\) then \(b \equiv a \pmod{n}\).

3. If \(a \equiv b \pmod{n}\) and \(b \equiv c \pmod{n}\), then \(a \equiv c \pmod{n}\).

In other words, congruence modulo \(n\) is reflexive, symmetric, and transitive, and so is an equivalence relation.

You should take a minute to convince yourself that each of the properties above actually holds for congruence. Try explaining each using both the remainder and divisibility definitions.

Next, consider how congruence behaves when doing basic arithmetic. We already know that if you subtract two congruent numbers, the result will be congruent to 0 (be a multiple of \(n\)). What if we add something congruent to 1 to something congruent to 2? Will we get something congruent to 3?

Suppose \(a \equiv b \pmod{n}\) and \(c \equiv d \pmod{n}\). Then the following hold:

1. \(a+c \equiv b+d \pmod{n}\)
2. \(a-c \equiv b-d \pmod{n}\)
3. \(ac \equiv bd \pmod{n}\)

The above facts might be written a little strangely, but the idea is simple. If we have a true congruence, and we add the same thing to both sides, the result is still a true congruence. This sounds like we are saying:

If \(a \equiv b \pmod{n}\) then \(a+c \equiv b+c \pmod{n}\).

Of course this is true as well; it is the special case where \(c = d\). But what we have works in more generality. Think of congruence as being basically equal. If we have two numbers that are basically equal, and we add basically the same thing to both sides, the result will be basically equal.

This seems reasonable. Is it really true? Let's prove the first fact:

The other two facts can be proved in a similar way.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Now that we have some algebraic rules to govern congruence relations, we can attempt to solve for an unknown in a congruence. For example, is there a value of \(x\) that satisfies, \[3x + 2 \equiv 4 \pmod{5}\], and if so, what is it?

In this example, since the modulus is small, we could simply try every possible value for \(x\). There are really only 5 to consider, since any integer that satisfied the congruence could be replaced with any other integer it was congruent to modulo 5. Here, when \(x = 4\) we get \(3x + 2 = 14\), which is indeed congruent to 4 modulo 5. This means that \(x = 9\) and \(x = 14\) and \(x = 19\) and so on will each also be a solution because, as we saw above, replacing any number in a congruence with a congruent number does not change the truth of the congruence.

So in this example, simply compute \(3x + 2\) for values of \(x \in \{0,1,2,3,4\}\). This gives 2, 5, 8, 11, and 14 respectively, for which only 14 is congruent to 4.

Let's also see how you could solve this using our rules for the algebra of congruences. Such an approach would be much simpler than the trial and error tactic if the modulus was larger. First, we know we can subtract 2 from both sides: \[3x \equiv 2 \pmod{5}\].

Then to divide both sides by 3, we first add 0 to both sides. Of course, on the right-hand side, we want that 0 to be a 10 (yes, \(10\) really is 0 since they are congruent modulo 5). This gives, \[3x \equiv 12 \pmod{5}\].

Now divide both sides by 3. Since \(\gcd(3,5) = 1\), we do not need to change the modulus: \[x \equiv 4 \pmod{5}\].

Notice that this in fact gives the general solution: Not only can \(x = 4\), but \(x\) can be any number which is congruent to 4. We can leave it like this, or write \(x = 4 + 5k\) for any integer \(k\).

The last congruence above illustrates the way in which congruences might not have solutions. We could have seen this immediately in fact. Look at the original congruence: \[20x \equiv 23 \pmod{14}\].

If \(\gcd(a,n) \nmid b\), then \(ax \equiv b \pmod{n}\) has no solutions.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Discrete math deals with whole numbers of things. So when we want to solve equations, we usually are looking for integer solutions. Equations that are intended to only have integer solutions were first studied by in the third century by the Greek mathematician Diophantus of Alexandria, and as such are called Diophantine equations. Probably the most famous example of a Diophantine equation is \(a^2 + b^2 = c^2\). The integer solutions to this equation are called Pythagorean triples. In general, solving Diophantine equations is hard (in fact, there is provably no general algorithm for deciding whether a Diophantine equation has a solution, a result known as Matiyasevich's Theorem). We will restrict our focus to linear Diophantine equations, which are considerably easier to work with.

An equation in two or more variables is called a Diophantine equation if only integer solutions are of interest. A linear Diophantine equation takes the form \(a_1x_1 + a_2x_2 + \cdots + a_nx_n = b\) for constants \(a_1,\ldots, a_n, b\).

A solution to a Diophantine equation is a solution to the equation consisting only of integers.

We have the tools we need to solve linear Diophantine equations. We will consider, as a main example, the equation \[51x + 87y = 123\].

The general strategy will be to convert the equation to a congruence, and then solve that congruence. This is certainly not the only way to proceed. A more common technique would be to apply the Euclidean algorithm. Our way can be a little faster, and is presented here primarily for variety. Let's work through this particular example to see how this might go.

First, check if perhaps there are no solutions because a divisor of \(51\) and \(87\) is not a divisor of \(123\). Really, we just need to check whether \(\gcd(51, 87) \mid 123\). This greatest common divisor is 3, and yes \(3 \mid 123\). At this point, we might as well factor out this greatest common divisor. So instead, we will solve: \[17x + 29y = 41\].

Now observe that if there are going to be solutions, then for those values of \(x\) and \(y\), the two sides of the equation must have the same remainder as each other, no matter what we divide by. In particular, if we divide both sides by 17, we must get the same remainder. Thus we can safely write \[17x + 29y \equiv 41 \pmod{17}\].

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.