2.1: A Taste of Number Theory

Before you get started, make sure you have read Chapter 1, which sets the tone for the work we will begin doing here. In addition, you might find it useful to read Appendix A: Elements of Style for Proofs. As stated at the end of Section 1.5, you are encouraged to review this appendix occasionally as you progress through the book as some guidelines may not initially make sense or seem relevant.

It is important to point out that we are diving in head first here. As we get started, we are going to rely on your intuition and previous experience with proofs. This is intentional. What you will likely encounter is a general sense of what a proof entails, but you may not be able to articulate the finer details that you do and do not comprehend. There are going to be some subtle issues that you will be confronted with and one of our goals will be to elucidate as many of them as possible. We need to calibrate and develop an intellectual need for structure. You are encouraged to just try your hand at writing proofs for the problems in this section without too much concern for whether you are “doing it the right way.” In Section 2.2, we will start over and begin to develop a formal foundation for the material in the remainder of the book. Once you have gained more experience and a better understanding of what a proof entails, you should consider returning to this section and reviewing your first attempts at writing proofs. In the meantime, see what you can do!

In this section, we will introduce the basics of a branch of mathematics called number theory, which is devoted to studying the properties of the integers. The integers is the set of numbers given by \[Z:={...,−3,−2,−1,0,1,2,3,...}.\]

The collection of positive integers also have a special name. The set of natural numbers is given by \[N:={1,2,3,...}.\]

Some mathematicians (set theorists, in particular) include 0 in N, but this will not be our convention. If you look closely at the two sets we defined above, you will notice that we wrote \(:=\) instead of =. We use := to mean that the symbol or expression on the left is defined to be equal to the expression on the right. The symbol R is used to denote the set of all real numbers. We will not formally define the real numbers, but instead rely on your prior intuition and understanding.

Because you are so familiar with many of the properties of the integers and real numbers, one of the issues that we will bump into is knowing which facts we can take for granted. As a general rule of thumb, you should attempt to use the definitions provided without relying too much on your prior knowledge. The order in which we develop things is important.

It is common practice in mathematics to use the symbol \(∈\) as an abbreviation for the phrase “is an element of” or sometimes simply “in.” For example, the mathematical expression “n ∈ Z” means “n is an element of the integers.” However, some care should be taken in how this symbol is used. We will only use the symbol “∈” in expressions of the form \(a ∈ A\), where A is a set and a is an element of A. We will write expressions like \(a,b ∈ A\) as shorthand for “a ∈ A and b ∈ A.” We should avoid writing phrases such as “a is a number ∈ A” and “n ∈ integers”.

We will now encounter our very first definition. In mathematics, a definition is a precise and unambiguous description of the meaning of a mathematical term. It characterizes the meaning of a word by giving all the properties and only those properties that must be true. Check out Appendix B for a list of other mathematical terms that we should be familiar with.

Definition 2.1. An integer n is even if n = 2k for some k ∈ Z. An integer n is odd if n = 2k + 1 for some k ∈ Z.

Notice that we framed the definition of “even” in terms of multiplication as opposed to division. When tackling theorems and problems involving even or odd, be sure to make use of our formal definitions and not some of the well-known divisibility properties. For now, you should avoid arguments that involve statements like, “even numbers have no remainder when divided by two” or “the last digit of an even number is 0, 2, 4, 6, or 8.” Also notice that the notions of even and odd apply to zero and negative numbers. In particular, zero is even since 0 = 2 · 0, where it is worth emphasizing that the occurrence of 0 on the righthand side of the equation is an integer. As another example, we see that −1 is odd since −1 = 2(−1) + 1. Despite the fact that −1 = 2(−1/2), this does not imply that −1 is also even since −1/2 is not an integer. For the remainder of this section, you may assume that every integer is either even or odd but never both.

Our first theorem concerning the integers is stated below. A theorem is a mathematical statement that is proved using rigorous mathematical reasoning. As with most theorems in this book, your task is to try your hand at proving the following theorem. Give it a try.

Theorem 2.2. If n is an even integer, then n² is an even integer.

One crux in proving the next theorem involves figuring out how to describe an arbitrary pair of consecutive integers.

Theorem 2.3. The sum of two consecutive integers is odd.

One skill we will want to develop is determining whether a given mathematical statement is true or false. In order to verify that a mathematical statement is false, we should provide a specific example where the statement fails. Such an example is called a counterexample. Notice that it is sufficient to provide a single example to verify that a general statement is not true. On the other hand, if we want to prove that a general mathematical statement is true, it is usually not sufficient to provide just a single example, or even a hundred examples. Such examples are just evidence that the statement is true.

Problem 2.4. Determine whether each of the following statements is true or false. If a statement is true, prove it. If a statement is false, provide a counterexample.

(a) The product of an odd integer and an even integer is odd.

(b) The product of an odd integer and an odd integer is odd.

(c) The product of an even integer and an even integer is even.

(d) The sum of an even integer and an odd integer is odd.

For the statements that were true in the previous problem, you may cite them later in a future proof as if they are theorems.

Definition 2.5. Given n,m ∈ Z, we say that n divides m, written \(n|m\), if there exists k ∈ Z such that m = nk. If n|m, we may also say that m is divisible by n or that n is a factor of m.

Problem 2.6. For n,m ∈ Z, how are the following mathematical expressions similar and how are they different? In particular, is each one a sentence or simply a noun?

(a) n|m

(b) \(\dfrac{m}{n}\)

(c) m/n

In this section on number theory, we allow addition, subtraction, and multiplication of integers. In general, we avoid division since an integer divided by an integer may result in a number that is not an integer. The upshot is that we will avoid writing \(\dfrac{m}{n}\). When you feel the urge to divide, switch to an equivalent formulation using multiplication. This will make your life much easier when proving statements involving divisibility.

Theorem 2.7. The sum of any three consecutive integers is always divisible by three.

Problem 2.8. Let a,b,n,m ∈ Z. Determine whether each of the following statements is true or false. If a statement is true, prove it. If a statement is false, provide a counterexample.

(a) If a|n, then a|mn.

(b) If 6 divides n, then 2 divides n and 3 divides n.

(c) If ab divides n, then a divides n and b divides n.

A theorem that follows almost immediately from another theorem is called a corollary. See if you can prove the next result quickly using a previous result. Be sure to cite the result in your proof.

Corollary 2.9. If a,n ∈ Z such that a divides n, then a divides n². The next two theorems are likely familiar to you.

Theorem 2.10. If a,n ∈ Z such that a divides n, then a divides −n.

Theorem 2.11. If a,n,m ∈ Z such that a divides m and a divides n, then a divides m + n.

Notice that we have been tinkering with statements of the form “If. . . , then. . . ”. Statements of this form are called conditional propositions, which we revisit in the next section. The phrase that occurs after “If” but before “then” is called the hypothesis while the phrase that occurs after “then” is called the conclusion. For example, in Problem 2.8(a), “a|n” is the hypothesis while “a|mn” is the conclusion. Note that conditional propositions can also be written in the form “. . . if . . . ”, where the conclusion is written before “if” and the hypothesis after. For example, we can rewrite Problem 2.8(a) as “a|mn if a|n”. While the order of the hypothesis and conclusion have been reversed in the sentence, their roles have not.

Whenever we encounter a conditional statement in mathematics, we want to get in the habit of asking ourselves what happens when we swap the roles of the hypothesis and the conclusion. The statement that results from reversing the roles of the hypothesis and conclusion in a conditional statement is called the converse of the original statement. For example, the converse of Problem 2.8(a) is “If a|mn, then a|n”, which happens to be false.The converse of Theorem 2.2 is “If n² is an even integer, then n is an even integer”. While this statement is true it does not have the same meaning as Theorem 2.2.

Problem 2.12. Determine whether the converse of each of Corollary 2.9, Theorem 2.10, and Theorem 2.11 is true. That is, for a,n,m ∈ Z, determine whether each of the following statements is true or false. If a statement is true, prove it. If a statement is false, provide a counterexample.

(a) If a divides n2 , then a divides n. (Converse of Corollary 2.9)

(b) If a divides −n, then a divides n. (Converse of Theorem 2.10)

(c) If a divides m + n, then a divides m and a divides n. (Converse of Theorem 2.11)

The next theorem is often referred to as the transitivity of division of integers.

Theorem 2.13. If a,b, c ∈ Z such that a divides b and b divides c, then a divides c.

Once we have proved a few theorems, we should be on the look out to see if we can utilize any of our current results to prove new results. There is no point in reinventing the wheel if we do not have to.

Theorem 2.14. If a,n,m ∈ Z such that a divides m and a divides n, then a divides m − n.

Theorem 2.15. If n ∈ Z such that n is odd, then 8 divides n² − 1.