Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 tried to start by showing that $ \frac{a}{\gcd(a,b)} $ is always an integer, let's call it $d$, because $a$ is always a multiple of $(a,b)$ based on the definition of a g.c.d. I then tried to show that if $a | b$ then $a|bc$ from the theorem that states that $a|b$ implies that $a|bc$ for any integer $c$, but I cant seem to prove that $a | b$ or that $a|bc$ only if $d \mid c$ (where $d = \frac{a}{\gcd(a,b)}$ ). Any help would be much appreciated.

share|cite|improve this question
up vote 5 down vote accepted

Note that $x|y$ if and only if $(x,y) = x$; then use the properties of the gcd.

\begin{align*} a|bc &\Longleftrightarrow (a,bc) = a\\ &\Longleftrightarrow \left(\frac{a}{(a,b)}, \frac{bc}{(a,b)}\right) = \frac{a}{(a,b)}\\ &\Longleftrightarrow \left(\frac{a}{(a,b)}, \frac{b}{(a,b)}c\right) = \frac{a}{(a,b)}\\ &\Longleftrightarrow \left(\frac{a}{(a,b)}, c\right) = \frac{a}{(a,b)}&&\mbox{(by Euclid's Lemma)}\\ &\Longleftrightarrow \frac{a}{(a,b)} \Bigm| c, \end{align*} using Euclid's Lemma ("If $(x,y)=1$, then $x|yz\Leftrightarrow x|z$") and $$1 = \frac{1}{(a,b)}(a,b) = \left(\frac{a}{(a,b)},\frac{b}{(a,b)}\right).$$

The manipulations are consequences of $x(y,z) = (xy,xz)$; see Bill Dubuque's proof here.

share|cite|improve this answer
How did you get rid of $\frac{b}{(a,b)}$ in between the third and fourth line? – Katie Barosie Feb 2 '11 at 19:24
@Katie: $(\frac{a}{(a,b)},\frac{b}{(a,b)}) = 1$; so the down-implication follows from Euclid's Lemma mentioned later. – Arturo Magidin Feb 2 '11 at 19:31

$$a\mid bc \Longleftrightarrow \frac{a}{(a,b)}\mid c$$



$a\mid bc\Rightarrow\exists k\in\mathbb{N}$ such that $bc=ak$$$bc=ak\Rightarrow\frac{bc}{(a,b)}=\frac{ak}{(a,b)}\Rightarrow\frac{b}{(a,b)}c=\frac{a}{(a,b)}k\Longrightarrow$$$$\frac{a}{(a,b)}\mid\frac{b}{(a,b)}c$$

Two theorems that we will use $$\text{If}\;\;x\mid yz\;\;\text{and}\;\;(x,y)=1\Longrightarrow x\mid z\;\;\;\;(\text{Theorem}\;*)\\\text{and}\\(\frac{x}{(x,y)},\frac{y}{(x,y)})=1\;\;\;\;(\text{Theorem}\;**)$$

Returning to the question, we have $$\frac{a}{(a,b)}\mid\frac{b}{(a,b)}c$$ by theorems $*$ and $**$ we have $$\frac{a}{(a,b)}\mid c\;\;\;\;\;\Box$$


$$\frac{a}{(a,b)}\mid c\Longrightarrow a\mid bc$$

$$\frac{a}{(a,b)}\mid c\Longrightarrow\exists k'\in\mathbb{N}\;\;\text{such that}\;\; c=\frac{a}{(a,b)}\cdot k'\\bc=\frac{ab}{(a,b)}\cdot k'\Longrightarrow bc=a(\frac{b}{(a,b)}\cdot k')\Longrightarrow a\mid bc\;\;\;\;\;\Box$$

share|cite|improve this answer

It is easy: $\rm\ \ a\: |\: bc\: \iff\: a\: |\: ac,bc\: \iff\: a\: |\: (ac,bc) = (a,b)\:c\: \iff\: a/(a,b)\: |\: c\quad$ QED

Or, dually: $\rm\ a\: |\: bc\: \iff\: a,b\: |\: bc\: \iff\: [a,b]\: |\: bc\: \iff\: [a.b]/b\ |\ c\:,\ $ $\rm\ [m,n]\: :=\ lcm(m,n)$

Combining the two yields the GCD $\cdot$ LCM law: $\rm\ [a,b]/b\: =\: a/(a,b)\:,\ $ i.e. $\rm\ (a,b)\ [a,b] =\: ab\:.$

Alternatively, cancelling $\rm\ (a,b)\ $ reduces it to Euclid's Lemma $\rm\ (a,b)= 1,\ a\:|\:bc\ \Rightarrow\ a|c\:.$

Above we used the $\: $ GCD $\: $ distributive law $\rm\: \ (ac,bc)\: =\: (a,b)\:c\:. \ $ For a proof see here.

More generally the result is the special case $\rm\ a\:|\:bc\ $ of $\rm\ (a,bc) = (a,(a,b)\:c)\:,\:$ which holds true for both GCDs and ideals. As you can see these basic properties are all intimately connected, so it's useful to master these properties to become proficient with GCD arithmetic. For another example of applying these properties to obtain simple proofs see this proof of the Freshman's Dream $\rm\ (A,B)^n = (A^n,B^n)\ $ for GCDs and invertible ideals.

share|cite|improve this answer

Your Answer


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