# FOM Assignment

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 $\mathbb{Z}$) of those natural numbers, i.e. that

$\text{gcd}(a,b) = ak+ bl$

for some integers $k, l \in \mathbb{Z}$

(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 $d$ can’t be a larger common divisor of $a$ and $b$ than $\text{gcd}(a,b)$, so $d = \text{gcd}(a,b)$.

(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 $a\equiv b (\text{mod} 10) \iff a \equiv b (\text{mod} 2) \text{ and } a \equiv b (\text{mod} 5)$.

Problem 4.  For this question we need to define some new notation.  Let $a \in \mathbb{Z}$ denote some integer.  Then we define the set $a\mathbb{Z}$ as

$a\mathbb{Z} = \{ax : x \in \mathbb{Z}\} = \text{ the set of all "}a\text{" multiples}$

(a) Prove that $2\mathbb{Z} \cap 3\mathbb{Z} = 6\mathbb{Z}$.

(b) Prove that if $m, n \in \mathbb{Z}$, then $mn\mathbb{Z} \subseteq m\mathbb{Z} \cap n\mathbb{Z}$.

(c ) Part (a) of this problem shows that for certain values of $m$ and $n$, the set containment from part (b) can “go the other way,” i.e. some times it is true that $m\mathbb{Z} \cap n \mathbb{Z} \subseteq mn \mathbb{Z}$.  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 $B \neq \emptyset$ and $A\times B \subseteq C\times B$.  Prove that $A \subseteq C$.

Problem 6.  Prove that for all $n \in \mathbb{N}$ the following equation is true:

$1^3 + 2^3 + \cdots + n^3 = \frac{n^2(n+1)^2}{4}$.

Problem 7. Prove that $n^3 + 5n$ is divisible by 6 for all $n \in \mathbb{N}$.

Problem 8.  Consider the function $f:\mathbb{R}\to\mathbb{R}$ given by $f(x) = \sqrt{2x}$.

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

$f^{(2)}(x) = (f\circ f)(x) = f(f(x))= f(\sqrt{2x}) = \sqrt{2\sqrt{2x}}$.

Similarly, $f^{(3)}(x)$ denotes the function composed with itself three times and, more generally, $f^{(k)}(x)$, denotes the function composed with itself $k$-times (where $k \in \mathbb{N}$).

(a) Consider the set

$S = \{f^{(k)}(1) : k \in \mathbb{N} \} = \{f(1), f(f(1)), f(f(f(1))), \cdots \}$.

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

(b) Prove that $f^{(n+1)}(1) \geq f^{(n)}(1)$ for all $n \in \mathbb{N}$.

(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 $S$ above, this means that there exists a real number $L \in \mathbb{R}$ so that

$\displaystyle \lim_{n\to\infty} f^{(n)}(1) = L$.

Prove that $L = 2$.

Problem 9.  Consider the relation $R = \{(a, b), (a, c), (c, c), (b, b), (c, b), (b, c)\}$ from the set $A = \{a, b, c\}$ to the set $A$ again.

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

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

Problem 10.  Define the relation $\sim$ on the set $\mathbb{R}^2$ by

$(x,y) \sim (a, b) \iff x^2 + y^2 = a^2 + b^2$.

(a) Prove that $\sim$ is an equivalence relation.

(b) Describe and draw a picture of the equivalence class $[(0,0)]$.

(c ) Describe and draw a picture of the equivalence class $[(0, 1)]$.