### Unit 3: Introduction to Number Theory and Proof Methods

In this unit, we will learn the properties of integers, real numbers, rational numbers, irrational numbers, and operations on all of these types of numbers. Our goal will be to learn how to determine the validity or falsity of a mathematical statement via a number of methods, including counterexample and exhaustion. We will apply these methods to not only prove the validity of the properties of the number types we are studying in this unit, but provide a practical approach to them so that future mathematical arguments can be proved or disproved using these methods.

**Completing this unit should take you approximately 11 hours.**

Upon successful completion of this unit, you will be able to:

- apply the rules of logic and proof techniques to mathematical statements involving odd and even, prime, rational, and irrational numbers; and
- prove and apply properties of divisibility.

### 3.1: Direct Proofs and Indirect Proofs

Read the opening discussion, "Proofs," Section 1, "The Axiomatic Method," and Sections 2 - 6, inclusive. In Unit 3, you will get a chance to apply a lot of what you have thought about and mastered in Units 1 and 2. Our domain of discourse is number theory, in particular proofs in elementary number theory.

Consider the following comparison of direct and indirect proofs. A direct proof is an argument that shows that the conclusion logically follows from the premises or assumptions by applying rules of inference in a sequence of steps.

Sections 1, 2, 4, and 5 deal with direct proofs. Section 2, "Proving an Implication," refers to statement such as P implies Q, and proving that Q is a consequence of P. In a logic system, P logically follows from the axioms and valid statements of the logic system, is another way of saying that P is a consequence of the axioms and valid statements or P is implied by them. This is what is meant by proving an implication.

Section 3 is related to indirect proof. Section 6 discusses indirect proof, also known as proof by contradiction, directly. An indirect proof, in contrast, is a proof in which the theorem to be proved is assumed false, and from this assumption, it is shown that a contradiction follows. Because the logic system is consistent, i.e. there are no contradictions, the theorem must be true. (Two statements are contradictions when they cannot both be true, and they cannot both be false.)

Read example 1 through example 4 on pages SF-3 to SF-6. It discusses proofs for sets.

### 3.1.1: Odd and Even Numbers

Read Section 1 through example 1 on pages NT-1 and NT-2. There are several commonly used sets of numbers that will be introduced to you; the first is the set of odd and even integers, i.e. the set of integers.

### 3.1.2: Prime Numbers

Read Section 1 beginning at "Prime Numbers and Factorization" on page NT-3, and continue up to example 3 on page NT-4. Example 3 also applies to 3.1.4 and 3.2.2 below. Prime numbers are the next set of commonly used numbers to be introduced. The introduction of prime numbers leads to the discussion of factoring an integer.

### 3.1.3: Proving and Disproving Universal Statements

Statements often involve universal quantifiers. The following subunits examine ways used to prove or disprove such statements.

### 3.1.3.1: Proof by Using the Method of Exhaustion

Reread example 2 on page NT-2, with special attention to the proof method, called proof by induction (an exhaustive proof method). This reading discusses a universal statement, which is just a statement that involves universal quantification.

A statement may be provable by evaluating it or by manipulating the symbols using definitions, rules, and theorems to transform the statement to an equivalent statement. Use of truth tables to evaluate a statement is an example of the former. This is also an example of the Method of Exhaustion. If a Universal statement has a finite set for its bound variable (a variable that is quantified is bound and the set of values that it can take is its range or domain), then it can be proven by proving it for each value in the range of the bound variable. If the set is countable, a proof by induction may be applicable. Induction is studied in Unit 4 of this course. Equivalently, the Universal statement can be proved by showing that it is true for an arbitrary value.

### 3.1.3.2: Disproof by Counterexample

Read over the Exercises for Section 1 on pages NT-10 - NT-13. Note the use of counterexamples. A universally quantified statement may be false. It can be proven false by showing that there exists an instance of the universally bound variable for which the statement is false. The instance is called a counter example. Exercises often have useful information, also applicable outside of the exercise.

### 3.1.4: Proving and Disproving an Existential Statement

Read example 5 on pages NT-5 and NT-6. An existential statement can be proved directly by specifying the instance of the existentially bound variable that makes the statement true. To disprove an existential statement, transform its negation to an equivalent universal statement, by using the property where the negation of an existential quantifier becomes a universal quantifier, (negating there exists an x such that P(x) becomes for all x not P(x)). Then, prove the universal statement.

### 3.2: Numbers: Direct Proofs and Counterexamples

Logic has application to other parts of mathematics, not just to reasoning about the world. The following subunits apply logic to statements about numbers.

### 3.2.1: Rational Numbers

Read Section 1: "Basic Facts about Numbers," example 4 on page NT-5. This example proves an important property of rational numbers using a constructive proof technique. This reading also applies to the topic in subunit 3.2.3 of this course.

### 3.2.2: Irrational Numbers

Read Section 1: "Basic Facts about Numbers," example 5 on pages NT-5 and NT-6 and example 6 on pages NT-7 - NT-9. Example 5 proves a property of real numbers using counterexamples. Example 6 applies to integer, rational, and real numbers.

### 3.2.3: Proving Properties of Rational Numbers

Read the recitation on pages 1 - 5. These give more examples of proof techniques for numbers.

### 3.3: Divisibility: Direct Proofs and Counterexamples

### 3.3.1: Divisibility

### 3.3.1.1: Divisibility Definition

Read Section 1, "Divisibility" on pages 1 - 4 and Section 4, "The Greatest Common Divisor" on pages 7 - 12. This reading overlaps that of Bender and Williamson.

Read "Remainders and Modular Arithmetic," page NT-6 to the top of NT-9. Section 2 and Section 3 are motivational, and you should at a minimum scan over them. Note that these discussions in the readings pertain to integers. In considering divisors of zero as you read through these sections, remember that every integer a divides 0, since a · 0 = 0. This also holds for rational, irrational, and real numbers, since w · 0 = 0 for any real number w.

We say that division by zero is undefined. Why do we say that? Consider the following line of reasoning: suppose x is a non-zero number, and when it is divided by zero, the result is the specific number y. It can be proved that, if x / 0 = y, then x = 0 multiplied by y (i.e. x = 0 * y). But, then, x = 0 * y = 0, because any number multiplied by 0 is 0. However, we assumed that x was non zero, a contradiction.

If x were 0, then x / 0 = 0 / 0 = y. Again, this implies that 0 = 0 * y. This, in turn, implies that y could be any number. This is, again, a contradiction, because we assumed that y was a specific number.

Mathematical definitions and proofs are specified to adhere to certain rules. One of those rules is that results do not lead to contradictions. Therefore, we say that division by 0 is not defined.

Theorem 1 on page NT-3 states that for any given integer, > or = 2, can be written as the product of prime numbers. Each of these primes will be a divisor of the given integer.

### 3.3.1.2: Divisibility of Algebraic Expressions

Read Section 3, "A Divisibility Theorem."

### 3.3.2: Proving Properties of Divisibility

Review Lemma 1 in Section 1.1 on page 2. Then Read Section 5, "The Fundamental Theorem of Arithmetic," on pages 12 - 15. Finally, Read Section 1.2, which presents the Division theorem in its entirety on pages 2 - 5.

### Unit 3 Assessment

Take this assessment to see how well you understood this unit.

- This assessment
**does not count towards your grade**. It is just for practice! - You will see the correct answers when you submit your answers. Use this to help you study for the final exam!
- You can take this assessment as many times as you want, whenever you want.

- This assessment