Chapter 4 - Elementary number theory and methods of proof

When is an integer n even?

iff n equals twice some integer.

When is an integer n odd?

n equals twice some integer plus 1.

An integer n is prime iff

n > 1 and for all positive integers r and s, if n

An integer n is composite iff

n > 1 and n

Constructive proofs of existence

A proof that shows an object exists by explicitly constructing it (provide an example or a method to find it).

Existential generalisation

A rule of inference in logic that allows you to go from a specific instance to an existence statement (from a specific example, conclude that something exists).

Nonconstructive proof of existence

May prove existence without giving an explicit example (often by contradiction).

Disproof by counterexample

To disprove a statement of the form “∀x ∈ D, if P(x) then Q(x),” find a value of x in D for which the hypothesis P(x) is true and the conclusion Q(x) is false. Such an x is called a counterexample.

Generalising from the generic particular

To show that every element of a set satisfies a certain property, suppose x is a particular but arbitrarily chosen element of the set, and show that x satisfies the property.

Method of direct proof step 1

Express the statement to be proved in the form “For every x ∈ D, if P(x) then Q(x).” (This step is often done mentally.)

Method of direct proof step 2

Start the proof by supposing x is a particular but arbitrarily chosen element of D for which the hypothesis P(x) is true. (This step is often abbreviated “Suppose x ∈ D and P(x).”)

Method of direct proof step 3

Show that the conclusion Q(x) is true by using definitions, previously established results, and the rules for logical inference.

Existential Instantiation

If the existence of a certain kind of object is assumed or has been deduced, then it can be given a name, as long as that name is not currently being used to refer to something else in the same discussion.

A real number r is rational iff

It can be expressed as a quotient of two integers with a nonzero denominator.

Zero Product Property

If neither of two real numbers is zero, then their product is also not zero.

Number theory

The study of properties of integers.

If n and d are integers, n is divisible by d iff

n equals d times some integer and d ≠ 0.

Instead of “n is divisible by d” we can say

"n is a multiple of d", "d is a factor of n", "d is a divisor of n", or "d divides n".

For all integers n and d, d isn't divisible by n

n / d is not an integer

Standard factored form

An expression, often a quadratic, written as a product of its factors.

The quotient-remainder theorem

Given any integer n and positive integer d, there exist unique integers q and r such that n

n div d

The integer quotient obtained when n is divided by d.

n mod d

The nonnegative integer remainder obtained when n is divided by d.

If n and d are integers and d > 0

Then n div d

Parity

The property of an integer being either even or odd.

Method of Proof by Division into Cases

To prove a statement of the form “If A1 or A2 or … or An, then C” prove all of the following: "If A1 then C, If A2 then C … If An then C"

Absolute value

Represents the distance from zero on a number line and is always a non-negative value.

Lemma

A statement that does not have much intrinsic interest but is helpful in deriving other results.

The floor of x

The function that takes as input a real number x, and gives as output the greatest integer less than or equal to x.

The ceiling of x

The function that takes as input a real number x, and gives as output the greatest integer greater than or equal to x.

n div d

floor(n / d)

n mod d

n - d * floor(n / d)

Method of proof by contradiction step 1

Suppose the statement to be proved is false. That is, suppose that the negation of the statement is true.

Method of proof by contradiction step 2

Show that this supposition leads logically to a contradiction.

Method of proof by contradiction step 3

Conclude that the statement to be proved is true.

Method of proof by contraposition step 1

Express the statement to be proved in the form ∀x in D, if P(x) then Q(x). (This step may be done mentally.)

Method of proof by contraposition step 2

Rewrite this statement in the contrapositive form ∀x in D, if Q(x) is false then P(x) is false. (This step may also be done mentally.)

Method of proof by contraposition step 3

Prove the contrapositive by a direct proof. a. Suppose x is a (particular but arbitrarily chosen) element of D such that Q(x) is false. b. Show that P(x) is false.

Proposition

A statement that is somewhat less consequential but nonetheless worth writing down.