Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
@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
up vote 4 down vote accepted

Hint $\ \ \begin{eqnarray}\rm (c,d)\!&|&\rm\:c\:|\:a \\ \ \rm(c,d)\!&|&\rm\:d\:|\:b\end{eqnarray}\ \Rightarrow\rm\ (c,d)\:|\:a,b\:\Rightarrow\: (c,d)\:|\:(a,b)\ \ \ $ QED

For Euclid's Lemma $\rm\:(a,b)=1=(a,c)\:\Rightarrow\:(a,bc) = 1,\:$ note it 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.$

Thus for $\rm\:a_i = a,\ b_j = b\:$ we deduce $\rm\:(a^n,b^k) = 1.\:$

share|cite|improve this answer
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$.

share|cite|improve this answer
+1 This is really cool. – Derek Allums Jun 1 '12 at 22:55
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?

share|cite|improve this answer
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$.

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.