Discrete Mathematics

Front 1

Mathematical Proof

Back 1

A mathematical proof of the statement S is a sequence of logically valid statements that connect axioms, definitions, and other already validated statements into a demonstration of the correctness of S. The rules of logic and the axioms are agreed on ahead of time. At a minimum, the axioms should be independent and consistent. The amount of detail presented should be appropriated for the intended audience.

Front 2

The Natural Numbers

Back 2

The set of natural numbers is denoted by N, and is defined by

N = {0,1,2,3,4,...}

Front 3

The Integers

Back 3

The set of integers is denoted by Z, and is defined by

Z = {..., -4,-3,-2,-1,0,1,2,3,4,...}

Front 4

The Rational Numbers

Back 4

The set of rational numbers is denoted by Q, and is defined by

Q={p/q | peZ, qeZ, and q != 0}

Front 5

Irrational Numbers

Back 5

A real number that is not rational

Front 6

Divisible

Back 6

The integer a is divisible by the nonzero integer b if a=bc for some integer c. We denote this by b|a and also say that b divides a.

Front 7

Quotient Remainder Thm

Back 7

Let a and b be integers with b != 0. Then there exist unique integers q and r such that a = bq + r and 0 <= r < |b|

Front 8

Even and Odd

Back 8

An integer, n, is even if there exists an integer, k, such that n = 2k. An integer is odd if it is not even.

Front 9

Greatest Common Divisor

Back 9

Let a and b be integers that are not both 0. The gcd of a and b is a positive integer d such that

- d|a and d|b

- If c divides both a and b, then c|d

Denoted gcd(a,b)

Front 10

gcd(a,b)=as + bt

Back 10

Let a and b be integers such that at least one is not 0. Then there are integers, s and t, such that gcd(a,b) = as + bt.

Front 11

Prime, Composite

Back 11

A positive integer p, with p > 1, is said to be prime if its only positive integer divisors are 1 and p. A pos int n, n > 1, that is not prime is called composite. The int 1 is neither prime nor composite.

Front 12

The Fundamental Thm of Arithmetic

Back 12

Every integer n, with n >= 2, can be uniquely written as the product of primes in ascending order.

Front 13

Relatively Prime

Back 13

Positive integers a and b are relatively prime if gcd(a,b)=1

Front 14

Pythagorean Triple

Back 14

The set of integers {a, b, c} is called a Pyth triple if a^2 + b^2 = c^2. It is called a primitive Pyth trip if a, b, and c have no common prime factor.

Front 15

a -= b (mod m)

Back 15

We say that a is congruent to b, mod m, if m divides a - b. This is often expressed as: a-=b(mod m) if and only if there is an integer k for which a - b = km

Front 16

n!

Back 16

n (n-1)(n-2)

Front 17

Floor Function; Ceiling Function

Back 17

Floor and ceiling functions are defined for all real numbers x by

floor(x) = largest int in interval (x-1, x]

ceiling(x) = largest int in interval [x, x =1)

Front 18

The Inverse of a, mod m

Back 18

Let a be a nonzero integer. An integer ~a is said to be an inverse of a mod m if a(~a) -= 1 (mod m)

Front 19

Inverses mod m

Back 19

Let a, meZ with m > 1. Then

1) if gcd(c, m) >1, a has no inverse, mod m

2) if gcd(a, m) =1 then a has an inverse mod m.

3) if ~a and ^a are both inverses for a mod m, then ~a -= ^a (mod m)

Front 20

Euclidean Algorithm

Back 20

98 = 66 * (1) + 32

66 = 32 * (2) + 2

32 = 2 * (16) + 0

2 is gcd(66, 98)

Front 21

Chinese Remainder Thm

Back 21

Multiply all of the mods to get m.

Then M1 = 2730/3 = 910, 910*1 -= 1 (mod 3)

so on and so forth

So if x -= 2 (mod 3)

x = (2*910*1 + ~~~ + ~~~) = solution to linear congruences

Front 22

Fermat's Little Therom

Back 22

Let a, p e Z with p a prime. Then

a^p -= a (mod p)

and

a^(p-1) -=

1 (mod p) if gcd(a, p) = 1

0 (mod p) if gcd(a, p) != 1

Front 23

Mathematical Induction

Back 23

If {P(i)} is a set of statements such that

1) P(1) is true and

2) P(i) -> P(i + 1) for i >= 1

then P(k) is true for all positive integers k.

Front 24

Optimaility of Deferred Acceptance Algorithm

Back 24

The DAA produces an assignment that is optimal for every suitor.

Front 25

Infinitude of the Primes

Back 25

There is an infinite number of distinct primes

Front 26

0^0

Back 26

1

Front 27

The Well-Ordering Principle

Back 27

Every nonempty set of natural numbers has a smallest element.

Front 28

Proof of QRT

Back 28

Existence:

1) r = a-bq

2) S = {a-bq | q e Z and a - bq >= 0}

3) Nonempty: q is bq <= a, a-bq >= 0

4) Well Ordering implies smallest element

5) Let that element be a-bq0 and set r0 = a -bq0

6) Suppose r0 >= |b|.

7) Let q1 = q0 + |b|/b. (q0 +- 1 and bq1 = bq0 + |b|)

8) a = bq0 + r0 = bq0 + |b| + (r0 - |b|) = bq1 + (r0 - |b|)

9) Thus a=bq1+(r0-|b|) and (r0-|b|)>=0

10) (r0-|b|) part of S now, and r0 is greater since |b| is greater than 0, contradicting that r0 is smallest element of S

11) Instead of r0 >= |b|, we must conclude r0 < |b|, q0 and r0 meet reqs of thm, existence estabbed

Uniqueness:

1)a=bq2+r2 and bq3+r3

2)b(q3-q2)=r2-r3, 0 <= r2, r3 < |b|

3)0<=|r2-r3|<|b|

4)|b|>|r2-r3|=|b|*|q3-q2|>=0

5)Only true if q3-q2=0 and q's are ints, which implies q2=q3 and r2=r3 estabbing uniqueness

Front 29

Direct Proof

Back 29

Typical

Front 30

Trivial

Back 30

If Q is true, then imp true, if P is not, Q is still true, Trivial

Front 31

Indirect

Back 31

Prove Contrapositive

Front 32

By Cases Proof

Back 32

If multiple cases can be made out of a claim