Discrete Mathematics An Open Introduction, 4th Edition

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\text{,}$ it is possible that $a÷b$ gives a whole number. In this case, we say that $b$ divides $a\text{;}$ in symbols, we write $b\mid a\text{.}$ If this holds, then $b$ is a divisor or factor of $a\text{,}$ and $a$ is a multiple of $b\text{.}$ In other words, if $b\mid a\text{,}$ then $a=bk$ for some integer $k$ (this is saying $a$ is some multiple of $b$).

Notice that $m\mid n$ is a statement. It is either true or false. On the other hand, $n÷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\text{,}$ then we can write $m\nmid n\text{.}$

This last example raises a question: How might one decide whether $m\mid n\text{?}$ Of course, if you had a trusted calculator, you could ask it for the value of $n÷m\text{.}$ If it spits out anything other than an integer, you know $m\nmid n\text{.}$ 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\text{.}$ How close? Well, we want to be sure that if we multiply $m$ by the next larger integer, we go over $n\text{.}$

Since $13<1642\text{,}$ we can now safely say that $1642\nmid 136299\text{.}$

It turns out that the process we went through above can be repeated for any pair of numbers. We can always write the number $a$ as some multiple of the number $b$ plus some remainder. We know this because we know about division with remainder from elementary school. This is just a way of saying it using multiplication. Due to the procedural nature that can be used to find the remainder, this fact is usually called the division algorithm:

The idea is that we can always take a large enough multiple of $b$ so that the remainder $r$ is as small as possible. We do allow the possibility of $r=0\text{,}$ in which case we have $b\mid a\text{.}$

The division algorithm tells us that there are only $b$ possible remainders when dividing by $b\text{.}$ 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 Subsection .

All fun technical language aside, the idea is really simple. If two numbers belong to the same remainder class, then in some way, they are the same. That is, they are the same up to division by $b$. In the case where $b=5$ above, the numbers $8$ and $23\text{,}$ while not the same number, are the same when it comes to dividing by 5, because both have remainder $3\text{.}$

It matters what the divisor is: $8$ and $23$ are the same up to division by $5\text{,}$ but not up to division by $7\text{,}$ since $8$ has a remainder of 1 when divided by 7 while 23 has a remainder of 2.

Many books define congruence modulo $n$ slightly differently. They say that $a\equiv b(\mathrm{mod}n)$ if and only if $n\mid a-b\text{.}$ In other words, two numbers are congruent modulo $n\text{,}$ if their difference is a multiple of $n\text{.}$ So which definition is correct? It turns out that it doesn’t matter; they are equivalent.

So $a-b$ is a multiple of $n\text{,}$ or equivalently, $n\mid a-b\text{.}$

On the other hand, if we assume first that $n\mid a-b\text{,}$ so $a-b=kn\text{,}$ then consider what happens if we divide each term by $n\text{.}$ Dividing $a$ by $n$ will leave some remainder, as will dividing $b$ by $n\text{.}$ However, dividing $kn$ by $n$ will leave 0 remainder. So the remainders on the left-hand side must cancel out. That is, the remainders must be the same.

Thus we have:

It will also be useful to switch back and forth between congruences and regular equations. The above fact helps with this. We know that $a\equiv b(\mathrm{mod}n)$ if and only if $n\mid a-b\text{,}$ if and only if $a-b=kn$ for some integer $k\text{.}$ Rearranging that equation, we get $a=b+kn\text{.}$ In other words, if $a$ and $b$ are congruent modulo $n\text{,}$ then $a$ is $b$ more than some multiple of $n\text{.}$ This conforms with our earlier observation that all the numbers in a particular remainder class are the same amount larger than the multiples of $n\text{.}$

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:

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?

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:

Of course this is true as well; it is the special case where $c=d\text{.}$ 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.

One of the important consequences of these facts about congruences is that we can basically replace any number in a congruence with any other number it is congruent to. Here are some examples to see how (and why) that works:

The above example should convince you that the well-known divisibility test for 9 is true: The sum of the digits of a number is divisible by 9 if and only if the original number is divisible by 9. In fact, we now know something more: Any number is congruent to the sum of its digits, modulo 9.

³

This works for 3 as well, but definitely not for any modulus in general.

Let’s try another.

In the above example, we are using the fact that if $a\equiv b(\mathrm{mod}n)\text{,}$ then $a^p\equiv b^p(\mathrm{mod}n)\text{.}$ This is just applying property 3 a bunch of times.

While this doesn’t work, note that $3\equiv 7(\mathrm{mod}4)\text{.}$ We cannot divide $8$ by 6, but we can divide 8 by the greatest common factor of $8$ and $6\text{.}$ Will this always happen?

Suppose $ad\equiv bd(\mathrm{mod}n)\text{.}$ In other words, we have $ad=bd+kn$ for some integer $k\text{.}$ Of course $ad$ is divisible by $d\text{,}$ as is $bd\text{.}$ So $kn$ must also be divisible by $d\text{.}$ Now if $n$ and $d$ have no common factors (other than 1), then we must have $d\mid k\text{.}$ But in general, if we try to divide $kn$ by $d\text{,}$ we don’t know that we will get an integer multiple of $n\text{.}$ Some of the $n$ might get divided as well. To be safe, let’s divide as much of $n$ as we can. Take the largest factor of both $d$ and $n\text{,}$ and cancel that out from $n\text{.}$ The rest of the factors of $d$ will come from $k\text{,}$ no problem.

We will call the largest factor of both $d$ and $n$ the $gcd(d,n)\text{,}$ for greatest common divisor. In our example above, $gcd(6,8)=2$ since the greatest divisor common to 6 and 8 is 2.

In this example, since the modulus is small, we could simply try every possible value for $x\text{.}$ 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\text{,}$ 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\}\text{.}$ This gives 2, 5, 8, 11, and 14 respectively, for which only 14 is congruent to 4.

Notice that this in fact gives the general solution: Not only can $x=4\text{,}$ 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\text{.}$”

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\text{.}$ 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.

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.

We have now found all solutions to the Diophantine equation. For each $k\text{,}$ $x=-1-29k$ and $y=2+17k$ will satisfy the equation. We could check this for a few cases. If $k=0\text{,}$ the solution is $(-1,2)\text{,}$ and yes, $-17+2\cdot 29=41\text{.}$ If $k=3\text{,}$ the solution is $(-88,53)\text{.}$ If $k=-2\text{,}$ we get $(57,-32)\text{.}$

To summarize this process, to solve $ax+by=c\text{,}$ we,

Here is another example:

Of course you could do this switching back and forth between congruences and Diophantine equations as many times as you like. If you only used this technique, you would essentially replicate the Euclidean algorithm, a more standard way to solve Diophantine equations.