Final

Question 1

Definition of Divisibility

Answer 1

a|b iff a•c = b

Question 2

Properties of Divisibility

Answer 2

If a|b and a|c then a|(b+c)

If a|b and b|c then a|c

If a|b then a|b*c

Question 3

Division Algorithm

Answer 3

Let a ∈ Z, d ∈ Z+
Then there are unique integers q and r such that
a = d * q + r

Question 4

Modulus Congruence

Answer 4

If a, b ∈ Z and m ∈ Z+, then
a ≅ b (mod m) iff m|a-b

OR if

m | (b - a)

OR if

a = b + k * m
k ∈ Z

Question 5

Definition of GCD

Answer 5

gcd(a, b) = d
where d|a and d|b and
∀e != d, if e|a and e|b, then e

Question 6

Euclidean Algorithm

Answer 6

gcd(a,b) = gcd(b,rem(a,b))

Question 7

Linear Combination

Answer 7

If gcd(a,b) = c
then c = a * s + b * t
where s, t ∈ Z

Question 8

Arithmetic Series

Answer 8

Sn = n(2a + (n - 1)d) / 2

Really just the average of the 1st and last terms multiplied by n

Question 9

Geometric Series

Answer 9

Sn = a(1 - r^n)/(1 - r)

Question 10

Definition of a Prime #

Answer 10

an integer p > 1 that has only 1 and itself as (positive) factors

Question 11

Fundamental Theorem of Arithmetic

Answer 11

Every integer n > 1 can be written in a unique way as a nondecreasing product of primes

Question 12

Prime Theorem

Answer 12

If n is a composite, then n has a prime divisor that satisfies p ≤ √n

Question 13

Principle of Induction

Answer 13

To prove ∀n ∈ Z+, P(n):
Basis step: P(1)
Inductive step: show that ∀k ≥ 1 (P(k) -> P(k+1)) is true
i.e. assuming P(k), show P(k + 1)

Question 14

Well Ordering Principle

Answer 14

Every non-empty subset of Z+ has a minimum element

Question 15

Principle of Strong Induction

Answer 15

To prove ∀n ∈ Z+, P(n):
Basis step: P(1)
Inductive step: show that ∀k ≥ 1 (P(1) ^ P(2) ^ P(3) ^ … ^ P(n) -> P(k+1)) is true