WakeUp wrote: a) Let $f,g:\mathbb{Z}\rightarrow\mathbb{Z}$ be one to one maps. Show that the function $h:\mathbb{Z}\rightarrow\mathbb{Z}$ defined by $h(x)=f(x)g(x)$, for all $x\in\mathbb{Z}$, cannot be a surjective function. Here is a solution. Let $p_1,p_2,p_3,p_4,p_5$ be five distinct prime numbers. If $h$ is surjective, then for all $p_i, \: i=1,2,3,4,5$ there exist distinct integers $n_1,n_2,n_3,n_4,n_5$ satisfying $h(n_i)=p_i$ So, $f(n_i)g(n_i)=p_i$ Since $p_i$'s are prime numbers, for all $i$'s, either $|f(n_i)|=1$ or $|g(n_i)|=1$ So, by Pigeonhole Principle, either $f$ or $g$ takes the same value at different points, hence it cannot be one to one, and this finishes the proof.

b) There exists $x_0$ with $f(x_0) = 0$; Take $g(x_0) = h(x_0) = 0$. Enumerate the not-null integers as $n_1, n_2, \ldots$. Let $A_0 = \{x_0\}$. For $k\geq 1$ perform the following, starting with $k=1$. The set $F_k = \{ x \in \mathbb{Z} \ ; \ n_k \mid f(x)\}$ is infinite. Take $x_k \in F_k \setminus A_{k-1}$, define $g(x_k) = n_k$, $h(x_k) = f(x_k)/g(x_k)$, and $B_{k-1} = A_{k-1} \cup \{x_k\}$. Then take $y_k \in F_k \setminus B_{k-1}$, define $h(y_k) = n_k$, $g(x_k) = f(x_k)/h(x_k)$, and $A_k = B_{k-1} \cup \{y_k\}$. The sets $A_k$ are always finite, so the procedure may continue indefinitely. This ensures that the functions $g$ and $h$ take all integer values when $x$ runs over $\bigcup_{k\geq 0} A_k$, while always having $f(x) = g(x)h(x)$. For any $x \in \mathbb{Z} \setminus \bigcup_{k\geq 0} A_k$ (if not empty), take $g(x) = 1$ and $h(x)=f(x)$ (or any such combination of values as to have $f(x) = g(x)h(x)$).

(a) Suppose for the sake of contradiction that $h$ is surjective. Take five distinct prime numbers $p_1, p_2, p_3, p_4, p_5$ and five distinct integers $a_1, a_2, a_3, a_4, a_5$ such that $h(a_i) = p_i$ for all $1 \leq i \leq 5$. For each $i$, we clearly must have \[(f(a_i), g(a_i)) \in \{(1, p_i), (-1, -p_i), (p_i, 1), (-p_i, -1)\}\]only, so by pigeonhole principle two of the tuples $(f(a_i), g(a_i))$ must coincide, implying that $f$ and $g$ are not bijective, a contradiction. (b) We will first give an algorithm to construct surjective functions $p$, $q$ such that $x = p(x) q(x)$ for all integers $x$. Let $p(0) = q(0) = 0$. Let $\mathcal{S}$ be the empty set, and set $i = 1$ initially. Now let $u, v$ be the two smallest positive multiples of $i$ greater than $\operatorname{max} \mathcal{S}$, and let $p(u) = q(v) = i$, $q(u) = \frac{u}{i}$, $p(v) = \frac{v}{i}$, after which we add $u$ and $v$ to $\mathcal{S}$. Similarly, for negative numbers we let $\mathcal{S}$ be the empty set $i = -1$ and $u, v$ be the two largest negative multiples of $i$ less than $\operatorname{min} \mathcal{S}$, and we proceed similarly. For all $p(i), q(i)$ not defined by this procedure we can simply set those values to be anything satisfying $p(i) q(i) = i$. Now just setting $g(i) = p(j)$ and $h(i) = q(j)$ where $j$ is defined as $f(i)$ works.

(a) The answer is no. Suppose that $h$ is surjective, so $x,y,z$ exist such that $h(x)$, $h(y)$, and $h(z)$ are three distinct primes. Then, three of $f(x), f(y), f(z), g(x), g(y), g(z)$ must be $1$. However, since $f$ and $g$ are both bijective, this is a contradiction. (b) The answer is yes. We can simply assign values to $f$ and $g$ to make this work. Suppose for any $N\in \mathbb{Z}$, no $t$ has been chosen yet such that $f(t)=N$. Since there are infinitely many multiples of $N$ and we have assigned only a finite number of values to $f$ and $g$ so far, we can simply select a $t$ such that $h(t)=Nk$ such that $f(x)g(x)\neq Nk$ for any previous assignments of $f$ and $g$, so now we can let $f(t)=N$ and $g(t)=k$. Since we can repeat these steps with $f$ and $g$ indefinitely, we are able to force $f$ and $g$ to be surjective.

b) I will put my functions here: h(n)=\left\{ \begin{array}{ccc} 0 & \text{if} & f(n)=0 -1 & \text{if} & f(n)=1 3 & \text{if} & f(n)=3 \sqrt{f(n)} & \text{if} & \exists k\in\mathbb{Z}:k^2=f(n) -k & \text{if} & \exists k\in\mathbb{Z}^{+}:k(k+1)=f(n) 1 & \text{else} \end{array}\right. g(n)=\left\{ \begin{array}{ccc} 0 & \text{if} & f(n)=0 -1 & \text{if} & f(n)=1 1 & \text{if} & f(n)=3 \sqrt{f(n)} & \text{if} & \exists k\in\mathbb{Z}:k^2=f(n) -(k+1) & \text{if} & \exists k\in\mathbb{Z}^{+}:k(k+1)=f(n) n & \text{else} \end{array}\right. all the if's here are "else if", meaning you go from top to bottom until the condition on the right is right, then you look at the left side and figure out what the output is supposed to be (aops does not allow me to use latex so put it in a latex decoder)