Euclid's Lemma and $\gcd(a,b)=1\Rightarrow \gcd(a^n,b^k)= 1$ I'm solving some problems in Apostol's Intro to Analytic Number Theory. He asks to prove
$$(a,b)=1 \wedge c|a \wedge d|b\Rightarrow (c,d)=1$$
My take is
$$\tag 1(a,b)=1 \Rightarrow 1=ax+by$$
$$ \tag 2 c|a \Rightarrow a=kc$$
$$\tag 3d|b \Rightarrow b=jd$$
$$(1),(2),(3) \Rightarrow 1=ckx+djy=cx'+dy'\Rightarrow (c,d)=1$$
Is this correct or is something missing?
I intend to use something similar to prove 
$$\eqalign{
  & \left( {a,b} \right) = 1 \wedge \left( {a,c} \right) = 1 \Rightarrow \left( {a,bc} \right) = 1  \cr 
  & \left( {a,b} \right) = 1 \Rightarrow \left( {{a^n},{b^k}} \right) = 1;n \geqslant 1,k \geqslant 1 \cr} $$
so I'd like to know.
 A: Your answer to the problem is correct. There is another, very elegant approach using the universal property of $\mathrm{gcd}$, which I learned from this answer. The universal property of $\mathrm{gcd}$ is that
$$
x|(a,b)\qquad\Leftrightarrow \qquad x|a\quad\text{and}\quad x|b.
$$
Now the proof is as follows. Since $c|a$ we have $(c,d)|a$. Since $d|b$ we have $(c,d)|b$. Hence the universal property of $\mathrm{gcd}$ implies that $(c,d)|(a,b)$. Since $(a,b)=1$ it follows that $(c,d)=1$.

This approach can also be used to prove the second statement. Note that $$(a,bc)|(ac,bc)$$ because $(a,bc)$ divides $a$ (and hence $ac$) and $bc$. Also, we have that $(ac,bc)/c\ |\ (a,b)$ because $$\frac{(ac,bc)}{c}\left|\frac{ac}{c}\right.\qquad\text{and}\qquad\frac{(ac,bc)}{c}\left|\frac{bc}{c}\right.$$ It follows that $(a,bc)|(a,b)c=c$. Since we also have that $(a,bc)|a$, the universal property we get that $(a,bc)|(a,c)$ and therefore $(a,bc)=1$. The third statement follows from the second with induction on $n$ and $k$.
A: Hint $\ \ \begin{eqnarray}\rm (c,d)&\mid c\mid a\\ 
\rm(c,d)&\mid d\mid b\end{eqnarray}\ \Rightarrow\rm\ (c,d)\mid a,b\:\Rightarrow\: (c,d)\mid (a,b)\ \ \ $ QED
EL = Euclid's Lemma $\rm\:(a,b)=1=(a,c)\:\Rightarrow\:(a,bc) = 1,\:$ is a special case of
$$\rm\ (a,b,c) = 1\ \Rightarrow\ (a,b)(a,c) = (a(a,b,c),bc) = (a,bc) $$
Thus iterating EL: $\rm\:\ (a_i,b_j) = 1\:\Rightarrow\:(a_i,\prod b_j)=1\:\Rightarrow\:(\prod a_i,\prod b_j) = 1.$
Specializing $\rm\:a_i = a,\ b_j = b\:$ we deduce $\rm\:(a^n,b^k) = 1.\:$
A: It looks fine to me. But really, $a = ck$ and $b = dj$, then if $c$ and $d$ had a common factor, $a$ and $b$ would clearly have as well, right?
A: Yes your approach is indeed correct and is probably the right way to go.
For the first problem, all we need is that $mx + ny = r$ where $m,n,r \in \mathbb{Z}$ has integer solutions iff $(m,n) | r$.
Since $(a,b) = 1$, there exists $x,y \in \mathbb{Z}$ such that $ax + by = 1$. Since $c|a$, we have $a = ck_1$ and since $d|b$, we have $b = dk_2$. Hence, we get that $$ck_1x + dk_2y = 1.$$Hence, $(c,d) = 1$.
For the second problem,
As before, since $(a,b) = 1$, we have $x_1,y_1,x_2,y_2 \in \mathbb{Z}$, such that $ax_1 + by_1 = 1$ and $ax_2 + cy_2 = 1$. Multiplying both out we get that $(ax_1 + by_1)(ax_2 + cy_2) = 1$ i.e. $a(ax_1x_2 + by_1x_2 + cy_2x_1) + bc (y_1y_2) = 1$. Note that $(ax_1x_2 + by_1x_2 + cy_2x_1), y_1y_2 \in \mathbb{Z}$. Hence, we have $(a,bc) = 1$.
For the third problem,
We will first prove that $(a^n,b) = 1$ for all $n \geq 1$. This is proved by induction. Clearly, for $n=1$ it is true since we are already given that $(a,b) = 1$. Assume that it is true for all $n$ up to $m$ i.e. we have $(a^n,b) = 1$, $\forall n \in \{1,2,\ldots,m \}$. Hence, we have that $ax + by = 1$ and $a^m x_1 + b y_1 = 1$ for some $x,x_1,y,y_1 \in \mathbb{Z}$. Multiplying the two out, we get that $(ax + by) \times (a^m x_1 + b y_1) = 1$ i.e. $a^{m+1} (xx_1) + b (axy_1 + a^n y x_1 + byy_1) = 1$. Hence, we get that $(a^{m+1},b) = 1$. Hence, by induction, we have that $(a^n,b) = 1$, $\forall n \in \mathbb{N}$. Now fix an $n \in \mathbb{N}$, we need to prove that $(a^n,b^k) = 1$, $\forall k \in \mathbb{Z}^+$. This is done by inducting on $k$ as before i.e. call $a^n = A$ and then induct as before to prove that $(A,b^k) = 1$ $\forall k \in \mathbb{N}$, given that $(A,b) = 1$. Hence, we get that $(a^n,b^k) = 1$, $\forall k,n \in \mathbb{N}$, given $(a,b) = 1$.
A: I prefer to use factorization in prime numbers. If $a=p_1^{n_1}\cdot\ldots\cdot p_r^{n_r}$ and $b=p_1^{m_1}\cdot\ldots\cdot p_r^{m_r}$ then $(a,b)=p_1^{k_1}\cdot\ldots\cdot p_r^{k_r}$ with $k_i=\min \{n_i,m_i\}$. For example, if $(a,b)=1$ then $k_i=0$ for every $i=1,\ldots,r$, which is equivalent to $n_i=0$ or $m_i=0$. As $a^n=p_1^{n~n_1}\cdot\ldots\cdot p_r^{n~n_r}$ and $b^k=p_1^{k~m_1}\cdot\ldots\cdot p_r^{k~m_r}$, therefore $(a^n,b^k)=p_1^{l_1}\cdot\ldots\cdot p_r^{l_r}$ with $l_i=\min \{n~n_i,k~m_i\}=0$, and $(a^n,b^k)=1$.
In fact, Apostol's book makes exhaustive use of factorization in the initial chapters. 
