**Problem 1**. Read Proposition 7.1 (on page 126) from our “Book of Proof.” This Proposition claims that the greatest common divisor of two natural numbers can always be expressed as a “linear combination” (over ) of those natural numbers, i.e. that

for some integers

(a) Explain where the Well-Ordering Principle was used in this proof.

(b) Explain, in your own words, the last line of this proof, the one that states “But can’t be a larger common divisor of and than , so .

(c ) Rate the quality of this proof (on a scale of, say, 1 to 10).

**Problem 2**. What is a non-constructive proof?

**Problem 3**. Prove that .

**Problem 4**. For this question we need to define some new notation. Let denote some integer. Then we define the set as

(a) Prove that .

(b) Prove that if , then .

(c ) Part (a) of this problem shows that for certain values of and , the set containment from part (b) can “go the other way,” i.e. some times it is true that . Is this always true? Explain your answer, addressing the conditions under which you think it is true. For bonus points, write a full-blown proof.

**Problem 5**. Suppose and . Prove that .

**Problem 6. **Prove that for all the following equation is true:

.

**Problem 7**. Prove that is divisible by 6 for all .

**Problem 8**. Consider the function given by .

We can compose the function with itself to form new, “iterated” functions. For example,

.

Similarly, denotes the function composed with itself three times and, more generally, , denotes the function composed with itself -times (where ).

(a) Consider the set

.

Prove that is bounded by , i.e. that every element in is less than or equal to the real number .

(b) Prove that for all .

(c ) (bonus) A Theorem from a class called Real Analysis states that every increasing, bounded sequence of real numbers has a limit. When applied to our set above, this means that there exists a real number so that

.

Prove that .

**Problem 9**. Consider the relation from the set to the set again.

(a) Is an equivalence relation? If so, prove your answer. If not, explain which of the three equivalence relation properties it fails.

(b) Is a function from to ? If so, prove your answer. If not, explain why not.

**Problem 10**. Define the relation on the set by

.

(a) Prove that is an equivalence relation.

(b) Describe and draw a picture of the equivalence class .

(c ) Describe and draw a picture of the equivalence class .