Elementary Number Theory: Proofs and Integers

Elementary Number Theory and Methods of Proof

• This chapter covers fundamental concepts in number theory and the methods for proving mathematical statements in that field.
• Discovery and proof are interwoven throughout the problem-solving process.
• Attempting to justify why a statement is true can reveal its falsehood.

Section 4.1: Direct Proof and Counterexample I: Introduction

• A fundamental familiarity with basic algebraic laws is assumed.
• Properties of equality (reflexive, symmetric, transitive) are used.
• Integers are closed under addition, subtraction, and multiplication (this essentially means that the result of those operations on integers is also an integer).
• Most integer quotients are not integers.

Definitions

• An integer is even if it can be expressed as twice another integer.
• An integer is odd if it can be expressed as twice another integer plus 1.

Example 1: Even and Odd Integers

• 0 is an even integer.
• -301 is an odd integer.
• The product of two integers is even.
• The sum of an even and odd number is odd.
• Every integer is either even or odd.

Definitions (continued)

• Prime numbers are positive integers greater than 1 with only positive factors of 1 and itself.
• Composite numbers are positive integers greater than 1 that are not prime (i.e., they can be written as a product of two smaller positive integers).

Example 2: Prime and Composite Numbers

• 1 is not a prime number.
• Every integer greater than 1 is either prime or composite.
• The first six prime numbers are 2, 3, 5, 7, 11, and 13.
• The first six composite numbers are 4, 6, 8, 9, 10, and 12.

Proving Existential Statements

• An existential statement is true if at least one object in a domain satisfies the property.
• Constructive proofs find the object explicitly.
• Nonconstructive proofs show that an object exists without finding it.

Example 3: Constructive Proofs of Existence

• There exists an even integer that can be expressed as the sum of two prime numbers in two different ways.

Proving Existential Statements (continued)

• Nonconstructive proofs demonstrate existence by showing that assuming there is no such object leads to a contradiction.

Disproving Universal Statements by Counterexample

• A universal statement is proven false by finding a specific case (counterexample) that violates it.
• The process involves identifying a case where the hypothesis is true, but the conclusion is false.

Example 4: Disproof by Counterexample

• The statement "for all real numbers a and b, if a²=b², then a = b" is false due to counterexamples involving negative numbers.

Proving Universal Statements

• Universal statements often use exhaustion (checking all) to prove a statement true across a finite domain.
• Generalizing from the generic particular is commonly used for universal statements covering an infinite domain.

Example 5: The Method of Exhaustion

• The statement "for all even integers n, from 4 to 26, n can be written as a sum of two primes" is provable using a method of exhaustion.

Example 6: Generalizing from the Generic Particular

• An example demonstrating a mathematical "trick" that depends on the idea of generalizing from the generic particular, where each step is shown algebraically.

Proving Universal Statements (continued)

• Direct proof: show that the hypothesis implies the conclusion by using known or established properties
• Direct proof is based on the logical rule of implication. The fact that the only way an if-then statement is false is if the hypothesis is true and the conclusion is false, is leveraged to prove the statement is true.

Example 7: A Direct Proof of Theorem

• Proving that the sum of any two even integers is even using direct proof. This includes a formal restatement and steps in the proof.

Directions for Writing Proofs of Universal Statements

• Guidelines for crafting clear mathematical proofs, including detailed explanations and justifications for each step.

Example 8: Identifying the "Starting Point" and the "Conclusion to be Shown"

• Identifying the starting point and conclusion to be shown in a universal statement using an example with graph theory.

Showing That an Existential Statement is False

• To prove an existential statement is false, prove that its negation, a universal statement, is true.

Example 9: Disproving an Existential Statement

• Showing that there is no positive integer n such that n² + 3n + 2 is prime. The negation is proven universal, using a particular but arbitrarily chosen integer, showing that the resulting expression is always a product of integers that are greater than 1.

Conjecture, Proof, and Disproof

• Historical context of conjectures, including Fermat's last theorem and Goldbach's conjecture.
• Examples of conjectures that were later proven false (Euler's conjecture).

Common Mistakes in Writing Proofs

• Avoiding mistakes like arguing only from examples, using the same variable for different values, jumping to conclusions, circular reasoning, or conflating what is known with what is to be shown.
• Avoid imprecisely using the word "if" when "because" is intended.
• Understand that just because a statement works for a few cases doesn't mean it is true always.

Getting Proofs Started

• After grasping the method of direct proof, the starting points and conclusions can be established even from theorems not immediately understood. The proof's structure can be determined from the statement's linguistic construction.