Proofs

Question 1

The inite sequence {Fn}, n ∈ Z, n ≥ 0, defined recursively by F0 = 1, F1 = 1, and Fn = Fn−1 +Fn−2 for n ≥ 2
is called the

Answer 1

Fibonacci sequence.

Question 2

A predicate P(n) defined for n ∈ Z+ is proven true for all integers n ≥ n0 using the Principle of Strong
Mathematical Induction by doing the following:

Answer 2

1. Prove P(n0) is true.
2. Assume there exists some integer k ≥ n0 such that P(j) is true for every integer j such that n0 ≤ j ≤ k.
3. Demonstrate explicitly that P(k + 1) is true.
4. Conclude that P(n) is true for all integers n ≥ n0.

Question 3

Let x, y ∈ R and n ∈ Z+. Then,
(x + y)^n = the sum of n
i=0 (n,i)
x^(n−i) y^i
.

Answer 3

The Binomial Theorem

Question 4

Every nonempty subset of positive integers has a least element.

Answer 4

Well-Ordering Principle.

Question 5

Let a, b ∈ Z with b > 0. Then there exist unique integers q and r, with
0 ≤ r < b such that a = bq + r.

Answer 5

Quotient-Remainder Theorem

Question 6

Let a, b ∈ Z, at least one of which is nonzero. An integer d is called a _______ of a and b if d|a and
d|b.

Answer 6

common divisor

Question 7

A common divisior d or a and b is called the____ of a and b if d ≥ c for any other
common divisor c of a and b.

Answer 7

Greatest common divisors

Question 8

If gcd(a, b) = 1, then a and b are

Answer 8

Relatively prime

Question 9

Let a, b ∈ Z, at least one of which is nonzero. If d = gcd(a, b), then there exist x, y ∈ Z so
that d = ax + by

Answer 9

Theorem 4.24.

Question 10

Two integers a and b, with at least one nonzero, satisfy gcd(a, b) = 1 if and only if there
exist x, y ∈ Z so that ax + by = 1.

Answer 10

Corollary 4.25

Question 11

If p is prime and p|ab for a, b ∈ Z, then p|a or p|b.

Answer 11

Euclid’s Lemma

Question 12

Every positive integer greater than 1 has a unique canonical form
prime factorization.

Answer 12

Fundamental Theorem of Arithmetic

Question 13

Let A and B be sets. A ____ R from A to B is a subset of A × B. We say a ∈ A is related to b ∈ B if
(a, b) ∈ R.

Answer 13

Relation

Question 14

Let R be a relation from A to B. The____ of R is (. )(R) = {a ∈ A|(a, b) ∈ R for some b ∈ B}. The ____ of R is Dom(R) = of R is Ran(R) = {b ∈ B|(a, b) ∈ R for some a ∈ A}

Answer 14

Domain, Range

Question 15

Let R be a relation from A to B. The_____to R, denoted by R−1, is the relation from B to A
defined by (b, a) ∈ R−1 if and only if (a, b) ∈ R.

Answer 15

inverse relation

Question 16

A relation R defined on a set A called an equivalence relation if and only if it satisfies all three of the
following properties:

Answer 16

1. R is reflexive: for every a ∈ A, (a, a) ∈ R.
2. R is symmetric: for every a, b ∈ A, if (a, b) ∈ R, then (b, a) ∈ R.
3. R is transitive: for every a, b, c ∈ A, if (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R.

Question 17

Let R be an equivalence relation defined on a set A. Then, for a ∈ A, the equivalence class of a determined
by R is the set___

Answer 17

[a] = {x ∈ A|(a, x) ∈ R}

Question 18

The set of equivalence classes of an equivalence relation R on a nonempty set A partitions A.

Answer 18

Theorem 5.16

Question 19

For m ∈ Z+, we say that a, b ∈ Z are

Answer 19

denoted a ≡m b (or a ≡ b mod m), if m|(a − b)

Question 20

Theorem 5.29. Suppose a, b, m ∈ Z with m > 0. The following statements are equivalent:

Answer 20

1. a ≡m b.
2. a and b have the same remainder when divided by m.
3. a = b + km for some k ∈ Z.

Question 21

For any m ∈ Z+, the relation ≡m is an equivalence relation on Z.

Answer 21

Corollary 5.31

Question 22

Theorem 5.34. Let m ∈ Z+, and assume ai ≡m bi for i = 1, 2. Then,

Answer 22

1. a1 + a2 ≡m b1 + b2
2. a1a2 ≡m b1b2, and 3. an1 ≡ mbn1 for all n ∈ Z, n ≥ 2

Question 23

A _____from a set X to a set Y is a relation from X to Y so that for every x ∈ X, there exists a unique
y ∈ Y such that (x, y) ∈ f.

Answer 23

Function f

Question 24

The set X is called the

Answer 24

domain of f

Question 25

The set Y is called the

Answer 25

Codomain

Question 26

The range of f is the set Ran(f)=

Answer 26

{f(x)|x ∈ X}

Question 27

Let f : X → Y be a function and A ⊆ X. The image of A under f is the set

Answer 27

f(A) = {b ∈ Y |∃a ∈ A such that f(a) = b} = {f(a)|a ∈ A}.

Question 28

Let f : X → Y be a function and B ⊆ Y . The inverse image of B under f is the set

Answer 28

f −1(B) = {a ∈ X|f(a) ∈ B}.

Question 29

A function f : X → Y is ____ if for every b ∈ Y , there exists an a ∈ X such that f(a) = b.

Answer 29

surjective or (onto)

Question 30

A function f : X → Y is ____if and only if for every a, b ∈ X, if a 6= b, then f(a) 6= f(b).

Answer 30

injective (or one-to-one)

Question 31

A function that is both injective and surjective is called a

Answer 31

Bijection

Question 32

True/False. If a statement is false, you should be able to provide a specific counterexample.
Examples.
* If a and b are integers such that [a]m = [b]m, then a = b.

Question 33

True/False. If a statement is false, you should be able to provide a specific counterexample: *If a, b, p are integers, with p prime, such that p|ab, then p|a or p|b.

Question 34

True/False. If a statement is false, you should be able to provide a specific counterexample: *Let a, b, m ∈Z+. If a ≡m b and a ≡n b, then a ≡mn b.