# 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.

• @DylanMoreland No, he doesn't. He uses "if" "and" "then", etc. I prefer $\wedge$. Why do you ask? – Pedro Tamaroff Jun 1 '12 at 23:38
• The proof, by the way, looks great. Most questions in elementary number theory come down to Bézout's identity, I think. – Dylan Moreland Jun 1 '12 at 23:39
• Wow, I can't follow this at all. Not surprising given my level of math training, but I'm trying to learn, and it's possible that I understand the concepts and am just being confused by the symbols. Would somebody please point me to a general overview of what this symbology is about? Even better, perhaps add a reference link to the elementary-number-theory tag wiki? Thanks. – Old Pro Jun 2 '12 at 3:09
• @OldPro I tend to use symbols when writing math. It is maybe a bad habit, but it helps me. Words tend to confuse me. $(a,b)$ is a number, namely the $\gcd$ of $a$ and $b$. $\wedge$ is a logical nexus meaning "and". $c|a$ means $c$ divides $a$. $a \Rightarrow b$ is to be read as "if $a$ then $b$". Hope you got it. – Pedro Tamaroff Jun 2 '12 at 3:26
• Thanks, Peter. Symbols are very hard to look up, and you had me confused because I recognized $\wedge$ and $\Rightarrow$ from logic but use $\wedge$ a bit differently and of course use | to mean "or" and not being into number theory didn't have a clue that $(a,b)$ was a single number. Not that I expect anyone to write questions like this in a way I understand them. Thank you for taking the time to explain. – Old Pro Jun 2 '12 at 3:34

## 5 Answers

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.\:$$

• How should I read $(c,d)|c|a$? – Pedro Tamaroff Jun 2 '12 at 0:11
• @PeterTamaroff $a|b|c$ is convenient shorthand for $a|b$ and $b|c$. You can extend this indefinitely: $d_1|d_2|d_3|\cdots$. This sort of writing would make an appearance, say, in the invariant factor decomposition of a finitely generated abelian group (which is number-theoretic). – anon Jun 2 '12 at 0:26
• Beautiful and elegant! – Eugene Jun 2 '12 at 0:27
• @Peter: Another thing you might want to know if you insist on writing symbols only is that statements of the form $x\Rightarrow y\Rightarrow z$, like the conclusion of the solution to your first question, are commonly taken to mean $x\Rightarrow(y\Rightarrow z)$, while you have meant $(x\Rightarrow y)\land(y\Rightarrow z)$ by it. – Egbert Jun 2 '12 at 0:30
• @Peter $\rm\ \ x\:|\:y\:|\:z\$ is a concise way of saying $$\rm x\:|\:y,\ y\:|\:z\ \Rightarrow\ x\:|\:z\ \ \ by\ transitivity\ of\ \ 'divides'$$ analogous to $\rm\:x \le y \le z.\quad$ – Bill Dubuque Jun 2 '12 at 15:05

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$.

• Because $(c,d)|c$ (and the divisibility relation is transitive). – Egbert Jun 1 '12 at 22:58

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?

• Sure. I like to keep it symbolic, though. =) – Pedro Tamaroff Jun 1 '12 at 22:45

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$.

• I'm asking about my proof. It's OK to have a new one, but what I want to know is if mine is legitimate. – Pedro Tamaroff Jun 1 '12 at 22:44

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.