I'm working through Oystein Ore's Number Theory and its History. On p. 109, I'm stuck on #2.

The question asks the reader to verify the following identity [Note: $(x,y)=\gcd(x,y)$]:


I've tried numerous numeric examples and not found an exception. I've tried a messy proof, substituting sample factors and exponents, but it's not very cohesive, clear, or robust. Clearly, if $a,b,c,d$ are all relatively prime, the answer is clear. I don't know how to concisely prove this if that's not the case though.

I've tried using the idea that $m(x,y)=(mx,my)$ to get rid of the denominators, but I still end up with some fractions. I've tried to use the symmetry of the fractions to simplify things. I also looked at this link without significant progress: Is $\gcd(a,b)\gcd(c,d)=\gcd(ac,bd)$?

  • $\begingroup$ You should post the question itself here, rather than just a reference to it. I'm guessing that many people won't have access to it otherwise. Edit: having found the book online the question is simply to verify the identity at the bottom. You should edit the post to make that clearer. $\endgroup$ – Rhys Steele Aug 12 '15 at 18:20
  • $\begingroup$ RJS is right. you should post the entire question as on this site, the users are from all over the world. Everyone should not have access to your reffered book. Ok, I saw one have downvoted you, I think for this reason. So, I am giving an upvoat nullify this because none knows this if the question is really inconvenient or not. $\endgroup$ – user249332 Aug 12 '15 at 18:50
  • $\begingroup$ Thank you. I've edited the post to indicate that the reader is asked to verify the given identity. $\endgroup$ – DBS Aug 12 '15 at 18:54
  • $\begingroup$ You are welcome. But, in future keep this in mind. $\endgroup$ – user249332 Aug 12 '15 at 18:56
  • $\begingroup$ A nice question. $\endgroup$ – user249332 Aug 12 '15 at 18:58

We first prove that if $\alpha,\beta,\gamma,\delta$ are integers such that $$(\alpha,\gamma)=(\alpha,\delta)=(\beta,\gamma)=(\beta,\delta)=1,$$ then $(\alpha\beta,\gamma\delta)=1.$ Indeed, from $(\alpha,\gamma)=1=(\alpha,\delta)$ we deduce that $(\alpha,\gamma\delta)=1.$ Similarly, from $(\beta,\gamma)=1=(\beta,\delta)$ it follows that $(\beta,\gamma\delta)=1.$ Combining the foregoing two results, we then conclude that $(\alpha\beta,\gamma\delta)=1.$

We then show that, if $(a,c)=1$ and $(b,d)=1,$ then $(ab,cd)=(a,d)(b,c).$ Indeed, because $(a,d)\mid a,$ $(b,c)\mid c,$ from $(a,c)=1$ we have $(a/(a,d), c/(b,c))=1.$ Similarly, from $(b,d)=1$ and $(b,d)\mid b, (a,d)\mid d,$ it follows that $(b/(b,c), d/(a,d))=1.$ It is also clear that $(a/(a,d), d/(a,d))=1$ and $(b/(b,c), c/(b,c))=1.$ Thus, by the foregoing paragraph, we have \begin{align*} (ab,cd)=&(a,d)(b,c)\left(\frac{a}{(a,d)}\frac{b}{(b,c)},\frac{d}{(a,d)}\frac{c}{(b,c)}\right)\\ =&(a,d)(b,c)\cdot 1=(a,d)(b,c), \end{align*} provided $(a,c)=1=(b,d).$

Now consider the general case. Because \begin{gather*} \left(\frac{a}{(a,c)},\frac{c}{(a,c)}\right)=1,\qquad \left(\frac{b}{(b,d)},\frac{d}{(b,d)}\right)=1, \end{gather*} we have \begin{align*} (ab,cd)&=\left((a,c)(b,d)\frac{a}{(a,c)}\frac{b}{(b,d)}, (a,c)(b,d)\frac{c}{(a,c)}\frac{d}{(b,d)}\right)\\ &=(a,c)(b,d)\left(\frac{a}{(a,c)}\frac{b}{(b,d)},\frac{c}{(a,c)}\frac{d}{(b,d)}\right)\\ &=(a,c)(b,d)\left(\frac{a}{(a,c)},\frac{d}{(b,d)}\right)\left(\frac{b}{(b,d)},\frac{c}{(a,c)}\right)\\ &=(a,c)(b,d)\left(\frac{a}{(a,c)},\frac{d}{(b,d)}\right)\left(\frac{c}{(a,c)},\frac{b}{(b,d)}\right). \end{align*}

  • $\begingroup$ I really like this answer and spent time to completely follow the logic. I'm vague on a couple points though. Up top, you show $(ab,cd)=(a,d)(b,c)$. Because we know $(a,c)=1$, then $$(a,cd)=(a,d);$$ and because we know $(b,d)=1$, then $$(b,cd)=(b,c).$$ We can combine those results as $(ab,cd)=(a,d)(b,c)$ even though $a,d$ and $b,c$ may not be relatively prime. Correct? The big term in parentheses in the first big equation $=1$ because of the logic of the second paragraph. $\endgroup$ – DBS Feb 24 '18 at 2:12
  • $\begingroup$ Down below, moving from the 3rd-to-last line to the 2nd-to-last line: We don't know the relationship of $a$ and $d$ in general, but because we know the identities you started the general case with, and using the idea I mentioned in my first comment, we can break the large parenthetic quantity in the 3rd-to-last line into the two smaller parenthetic quantities in the 2nd-to-last line. Correct? $\endgroup$ – DBS Feb 24 '18 at 2:13
  • $\begingroup$ @DBS: I have not used the statement you mensioned: $(a,c)=1$ implies $(a,cd)=(a,d).$ Actually, in Line 10 of my post, I have used the result which says that: $(mx,my)=m(x,y)$ for every positive integer $m,$ just letting $m=(a,d)(b,c).$ And what $x$ and $y$ are is not hard to determine. In Line 11, I have used the result of Line2-3. Also, you said that, combining $(a,cd)=(a,d)$ with $(b,cd)=(b,c)$ gives $(b,cd)=(a,d)(b,c).$ I think this result is not always true. And I have not used this. $\endgroup$ – azc Feb 24 '18 at 4:32
  • $\begingroup$ I probably overreached in trying to understand completely. Thanks for your time, and I'll study this some more. $\endgroup$ – DBS Feb 25 '18 at 2:39
  • $\begingroup$ Oh! Line 10 is $(mx,my)=m(x,y).$ That was one of my sticking points. And going from your third-to-last line to the second-to-last line is basically a reverse of the first paragraph. Thanks for your help and clarification. I think I now understand. $\endgroup$ – DBS Feb 25 '18 at 23:06

Theorem 1. Let $x$ and $y$ be two integers. Then, there exist integers $p$ and $q$ such that $px+qy=\gcd\left( x,y\right) $.

Theorem 1 is Bezout's theorem, and we assume it to be known. Notice that the integers $x$ and $y$ are allowed to be $0$ (even both of them, in which case we use the convention $\gcd\left( 0,0\right) =0$).

Proposition 2. Let $n$ and $m$ be two nonnegative integers such that $n\mid m$ and $m\mid n$. Then, $m=n$.

Proposition 2 is obvious. Equalities between gcd's are usually proven with the help of Proposition 2.

Lemma 3. Let $x$, $y$, $z$ and $w$ be four integers such that $\gcd\left( x,z\right) =1$ and $\gcd\left( y,w\right) =1$. Then, $\gcd\left( xy,zw\right) =\gcd\left( y,z\right) \cdot\gcd\left( x,w\right) $.

Proof of Lemma 3. Theorem 1 (applied to $w$ instead of $y$) shows that there exist integers $p$ and $q$ such that $px+qw=\gcd\left( x,w\right) $. Let us denote these $p$ and $q$ by $p_{1}$ and $q_{1}$. Thus, $p_{1}$ and $q_{1}$ are integers satisfying $p_{1}x+q_{1}w=\gcd\left( x,w\right) $.

Theorem 1 (applied to $y$ and $z$ instead of $x$ and $y$) shows that there exist integers $p$ and $q$ such that $py+qz=\gcd\left( y,z\right) $. Let us denote these $p$ and $q$ by $p_{2}$ and $q_{2}$. Thus, $p_{2}$ and $q_{2}$ are integers satisfying $p_{2}y+q_{2}z=\gcd\left( y,z\right) $.

Theorem 1 (applied to $z$ instead of $y$) shows that there exist integers $p$ and $q$ such that $px+qz=\gcd\left( x,z\right) $. Let us denote these $p$ and $q$ by $g$ and $h$. Thus, $g$ and $h$ are integers satisfying $gx+hz=\gcd\left( x,z\right) $. Hence, $gx+hz=\gcd\left( x,z\right) =1$.

Theorem 1 (applied to $y$ and $w$ instead of $x$ and $y$) shows that there exist integers $p$ and $q$ such that $py+qw=\gcd\left( y,w\right) $. Let us denote these $p$ and $q$ by $g^{\prime}$ and $h^{\prime}$. Thus, $g^{\prime}$ and $h^{\prime}$ are integers satisfying $g^{\prime}y+h^{\prime}w=\gcd\left( x,z\right) $. Hence, $g^{\prime}y+h^{\prime}w=\gcd\left( x,z\right) =1$.


$\underbrace{\gcd\left( y,z\right) }_{=p_{2}y+q_{2}z}\cdot\underbrace{\gcd \left( x,w\right) }_{=p_{1}x+q_{1}w}$

$=\left( p_{2}y+q_{2}z\right) \cdot\left( p_{1}x+q_{1}w\right) $

$=p_{1}p_{2}xy+q_{1}p_{2}\underbrace{yw}_{=yw1}+q_{2}p_{1}\underbrace{xz} _{=xz1}+q_{1}q_{2}zw$

$=p_{1}p_{2}xy+q_{1}p_{2}yw\underbrace{1}_{=gx+hz}+q_{2}p_{1}xz\underbrace{1} _{=g^{\prime}y+h^{\prime}w}+q_{1}q_{2}zw$

$=p_{1}p_{2}xy+q_{1}p_{2}yw\left( gx+hz\right) +q_{2}p_{1}xz\left( g^{\prime}y+h^{\prime}w\right) +q_{1}q_{2}zw$

$=p_{1}p_{2}xy+q_{1}p_{2}ywgx+q_{1}p_{2}ywhz+q_{2}p_{1}xzg^{\prime} y+q_{2}p_{1}xzh^{\prime}w+q_{1}q_{2}zw$

$=\left( p_{1}p_{2}+q_{1}p_{2}wg+q_{2}p_{1}zg^{\prime}\right) xy+\left( q_{1}p_{2}yh+q_{2}p_{1}xh^{\prime}+q_{1}q_{2}\right) zw$ (by a straightforward computation)

is a $\mathbb{Z}$-linear combination of $xy$ and $zw$, and therefore divisible by $\gcd\left( xy,zw\right) $ (since both $xy$ and $zw$ are divisible by $\gcd\left( xy,zw\right) $). In other words,

(1) $\gcd\left( xy,zw\right) \mid\gcd\left( y,z\right) \cdot \gcd\left( x,w\right) $.

On the other hand, multiplying the relations $\gcd\left( y,z\right) \mid y$ and $\gcd\left( x,w\right) \mid x$, we obtain $\gcd\left( y,z\right) \cdot\gcd\left( x,w\right) \mid yx=xy$. Also, multiplying the relations $\gcd\left( y,z\right) \mid z$ and $\gcd\left( x,w\right) \mid w$, we obtain $\gcd\left( y,z\right) \cdot \gcd\left( x,w\right) \mid zw$. We thus know that both $xy$ and $zw$ are divisible by $\gcd\left( y,z\right) \cdot\gcd\left( x,w\right) $. Therefore, the greatest common divisor of $xy$ and $zw$ is also divisible by $\gcd\left( y,z\right) \cdot\gcd\left( x,w\right) $. In other words, we have

(2) $\gcd\left( y,z\right) \cdot\gcd\left( x,w\right) \mid\gcd\left( xy,zw\right) $.

Now, we have proven (1) and (2). Thus, we can apply Proposition 2 to $n=\gcd\left( y,z\right) \cdot\gcd\left( x,w\right) $ and $m=\gcd\left( xy,zw\right) $. We thus obtain $\gcd\left( xy,zw\right) =\gcd\left( y,z\right) \cdot\gcd\left( x,w\right) $. This proves Lemma 3.

Theorem 4. Let $a$, $b$, $c$ and $d$ be four integers. Let $n=\gcd\left( a,c\right) $ and $m=\gcd\left( b,d\right) $; assume that $n\neq0$ and $m\neq0$. Then,

$\gcd\left( ab,cd\right) =\gcd\left( a,c\right) \cdot\gcd\left( b,d\right) \cdot\gcd\left( \dfrac{a}{n},\dfrac{d}{m}\right) \cdot \gcd\left( \dfrac{c}{n},\dfrac{b}{m}\right) $.

Proof of Theorem 4. Let $x=\dfrac{n}{a}$, $y=\dfrac{m}{b}$, $z=\dfrac{n}{c}$ and $w=\dfrac{n}{d}$. Then, $a=nx$, $b=my$, $c=nz$ and $d=nw$. Also, $x=\dfrac{n}{a}$ is an integer (since $n=\gcd\left( a,c\right) \mid a$), and similarly $y$, $z$ and $w$ are integers.

Now, $n=\gcd\left( \underbrace{a}_{=nx},\underbrace{c}_{=nz}\right) =\gcd\left( nx,nz\right) =n\gcd\left( x,z\right) $. Since $n\neq0$, we can divide this equality by $n$, and obtain $1=\gcd\left( x,z\right) $. The same argument (using $m,b,d,y,w$ instead of $n,a,c,x,z$) shows that $1=\gcd\left( y,w\right) $. Thus, Lemma 3 yields

$\gcd\left( xy,zw\right) =\underbrace{\gcd\left( y,z\right) } _{=\gcd\left( z,y\right) }\cdot\gcd\left( x,w\right) =\gcd\left( z,y\right) \cdot\gcd\left( x,w\right) $

$=\gcd\left( x,w\right) \cdot\gcd\left( z,y\right) $.


$\gcd\left( \underbrace{a}_{=nx}\underbrace{b}_{=my},\underbrace{c} _{=nz}\underbrace{d}_{=mw}\right) =\gcd\left( nxmy,nzmw\right) =\gcd\left( nm\cdot xy,nm\cdot zw\right) $

$=nm\cdot\underbrace{\gcd\left( xy,zw\right) }_{=\gcd\left( w,x\right) \cdot\gcd\left( z,y\right) }=\underbrace{n}_{=\gcd\left( a,c\right) }\underbrace{m}_{=\gcd\left( b,d\right) }\cdot\gcd\left( \underbrace{x} _{=\dfrac{a}{n}},\underbrace{w}_{=\dfrac{d}{m}}\right) \cdot\gcd\left( \underbrace{z}_{=\dfrac{c}{n}},\underbrace{y}_{=\dfrac{b}{m}}\right) $

$=\gcd\left( a,c\right) \cdot\gcd\left( b,d\right) \cdot\gcd\left( \dfrac{a}{n},\dfrac{d}{m}\right) \cdot\gcd\left( \dfrac{c}{n},\dfrac{b} {m}\right) $.

Theorem 4 is proven.

This is probably not the simplest or shortest proof, but was the easiest one to write (it took me almost no focus and very little editing, just a lot of copy & paste). The annoying computations in the proof of Lemma 3 could have been simplified using ideal notation, but I don't know if you have this background. There is certainly an alternative proof by comparing exponents of primes, but my kind of argument generalizes better. For example, Lemma 3 above can be straightforwardly generalized to the following result:

Lemma 5. Let $A$ be a commutative ring. Let $X$, $Y$, $Z$ and $W$ be four ideals of $A$ such that $X+Z=A$ and $Y+W=A$. Then, $XY+ZW = \left(Y+Z\right)\left(X+W\right)$.

Lemma 3 can be recovered from Lemma 5 by setting $A = \mathbb Z$, $X = x \mathbb Z$, $Y = y \mathbb Z$, $Z = z \mathbb Z$ and $W = w \mathbb Z$. The proof I gave for Lemma 3 is essentially a proof for Lemma 5, artificially restricted to the case of principal ideals in $\mathbb Z$. Theorem 4 is harder to generalize, since it is not clear what the analogue of (for example) $\dfrac{a}{n}$ is for ideals; but given that it is a corollary of Lemma 3, a point could be made in favor of regarding Lemma 3 as the main theorem.

  • $\begingroup$ Wow! I'm not familiar with Bezout's theorem, but I'll look into it. It will take me a little while to go through your answer. Thank you for your assistance. $\endgroup$ – DBS Aug 12 '15 at 20:35
  • $\begingroup$ Bezout's theorem is one of the most important properties of the gcd. It should be somewhere in the book you are reading. $\endgroup$ – darij grinberg Aug 12 '15 at 20:36
  • $\begingroup$ Surprisingly, I can't find it in there. I'll check online sources though. $\endgroup$ – DBS Aug 12 '15 at 20:40
  • $\begingroup$ Thank you for the proof. It looked overwhelming initially, but as I saw the pieces coming together in the proof of Theorem 4, it was quite powerful. I appreciate your computations in Lemma 3; you're correct that I'm not familiar with ideal notation. My attempts to verify the given identity were closer to what you mentioned (comparing exponents of primes), but your method is far more robust. I looked up Bezout's theorem and the definition of commutative ring. Thank you for the teaching! $\endgroup$ – DBS Aug 13 '15 at 17:02
  • $\begingroup$ @darijgrinberg Hey, Darij, it would be very nice, in case you could kindly There is certainly an alternative proof by comparing exponents of primes. Could you please detail out the proof?? $\endgroup$ – crskhr Jun 18 '16 at 14:50

After being away from the problem for more than a year, Leox's comment reminded me of the problem, so I looked at it again. I think I solved it! (EDIT: Per the comments, this answer is incomplete and has an error.) I use just the basic GCD (a,b) and LCM [a,b] identities presented in the book to that point: $$ab=(a,b)[a,b]$$ and $$(ma,mb)=m(a,b)$$ It's a bit involved, but I begin with the right side of the given identity and work to yield the left side. $$(a,c)(b,d)\left(\frac{a}{(a,c)},\frac{d}{(b,d)}\right)\left(\frac{c}{(a,c)},\frac{b}{(b,d)}\right)$$ Reorganize terms: $$=(a,c)\left(\frac{a}{(a,c)},\frac{d}{(b,d)}\right)(b,d)\left(\frac{c}{(a,c)},\frac{b}{(b,d)}\right)$$ Mulltiply first big parenthesis by $(a,c)$ and second by $(b,d)$: $$=\left(\frac{a(a,c)}{(a,c)},\frac{d(a,c)}{(b,d)}\right)\left(\frac{c(b,d)}{(a,c)},\frac{b(b,d)}{(b,d)}\right)$$ Simplify: $$=\left(a,\frac{d(a,c)}{(b,d)}\right)\left(\frac{c(b,d)}{(a,c)},b\right)$$ Substitute $1/(b,d)=[b,d]/bd$ and $1/(a,c)=[a,c]/ac$: $$=\left(a,d(a,c)\frac{[b,d]}{bd}\right)\left(c(b,d)\frac{[a,c]}{ac},b\right)$$ Cancel $d$'s from first term and $c$'s from second term and rewrite: $$=\left(a,\frac{(a,c)[b,d]}{b}\right)\left(\frac{(b,d)[a,c]}{a},b\right)$$ Treat the whole first term like $m$ in $m(a,b)=(ma,mb)$ and multiply it into the second term: $$=\left(\left(a,\frac{(a,c)[b,d]}{b}\right)\frac{(b,d)[a,c]}{a},\left(a,\frac{(a,c)[b,d]}{b}\right)b\right)$$ Multiply: $$=\left(\left(\frac{a(b,d)[a,c]}{a},\frac{(a,c)[b,d](b,d)[a,c]}{ba}\right),\left(ab,\frac{b(a,c)[b,d]}{b}\right)\right)$$ Simplify fractions, and note that $(a,c)[a,c]=ac$ and $[b,d](b,d)=bd$: $$=\left(\left((b,d)[a,c],\frac{acbd}{ba}\right),\left(ab,\frac{(a,c)[b,d]}{1}\right)\right)$$ $$=\bigg(\Big((b,d)[a,c],cd\Big),\Big(ab,(a,c)[b,d]\Big)\bigg)$$ Again note that $(a,c)[a,c]=ac$ and $[b,d](b,d)=bd$ to rewrite the individual GCD and LCM terms: $$=\bigg(\Big(\frac{bd}{[b,d]}\frac{ac}{(a,c)},cd\Big),\Big(ab,\frac{ac}{[a,c]}\frac{bd}{(b,d)}\Big)\bigg)$$ $$=\bigg(\Big(\frac{abcd}{[b,d](a,c)},cd\Big),\Big(ab,\frac{abcd}{[a,c](b,d)}\Big)\bigg)$$ Factor, using the idea $(ma,mb)=m(a,b)$: $$=\bigg(cd\Big(\frac{ab}{[b,d](a,c)},1\Big),ab\Big(1,\frac{cd}{[a,c](b,d)}\Big)\bigg)$$ I don't have a good answer why these fractions have to work out to be natural numbers, but algebraically that's the result when factored.

The GCD of 1 and any other natural number is 1: $$=\Big(cd*1,ab*1\Big)=\Big(cd,ab\Big)=\Big(ab,cd\Big)$$

  • $\begingroup$ You proof is not totally valid. Actually, if $a=2, b=3, c=5, d=4,$ then $\frac{ab}{[b,d](a,c)}=1/2,$ which is not an integer! $\endgroup$ – azc Feb 18 '18 at 3:09
  • $\begingroup$ That's frustrating -- I was concerned about that second-to-last step, but I couldn't find an obvious problem or counterexample -- which you did! Thank you. I wanted to do the proof using just the material presented in the book thus far. Perhaps this "answer" should be deleted, down-voted, or corrected if someone can make it valid. $\endgroup$ – DBS Feb 19 '18 at 14:03
  • $\begingroup$ I think it is sufficient to indicate the proof is not complete in the body of the answer $\endgroup$ – Rodrigo Apr 26 '19 at 23:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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