# Number Theoryj1.1.6 Suppose a and b are integers that divide the integer c

#### karush

##### Well-known member
Suppose a and b are integers that divide the integer c
If a and b are relatively prime, show that $ab / c$
Show by example that if a and b are not relatively prime,
then ab need not divide c
let
$$a=3 \quad b=5 \quad c=15$$
then
$$\frac{15}{3\cdot 5}=1$$
let
$$a=4 \quad b=6 \quad c=15$$
then
$$\frac{15}{4\cdot 6}\quad\textit{not an interger}$$

my feeble attempt Last edited by a moderator:

#### Greg

##### Perseverance
Staff member
If $a$ and $b$ are relatively prime then the prime factors of $ab$ must be in $c$. If $a$ and $b$ are not relatively prime then this is not necessarily true (by "prime factors" I mean exponentiation is included). Consider $8|72$, $9|72$ and $8*9|72$, but $8|72$, $24|72$ but $8*24\cancel{|}72$.

#### karush

##### Well-known member
so the $\vert$ means factor of

#### Olinguito

##### Well-known member
For any integers $a$ and $b$, if both divide another integer $c$, their lcm always divides $c$. If $\gcd(a,b)=1$, then $\mathrm{lcm}(a,b)=ab$.

#### Greg

##### Perseverance
Staff member
so the $\vert$ means factor of
Or $a|b\Rightarrow a\text{ divides }b$.

#### Olinguito

##### Well-known member
By the way the second line of the OP should read $ab\mid c$.

#### karush

##### Well-known member
By the way the second line of the OP should read $ab\mid c$.
yeah saw that
but too late to change

but mahalo

#### Olinguito

##### Well-known member
yeah saw that
but too late to change

but mahalo
ʻAʻole pilikia. Anyway, this result is a generalization of the OP:

Given nonzero integers $a$ and $b$ with lcm $m$ and gcd $d$, $dm=ab$.​

The lcm of $a$ and $b$ can be taken to be the least positive integer that is a common multiple of $a$ and $b$. We have the following lemma:

$m=\mathrm{lcm}(a,b)\ \iff\ a,b\mid m$ and for any $n\in\mathbb Z$, $a,b\mid n\implies m\mid n$.​

In other words, the lcm divides every other common multiple of $a,b$. The proof is straightforward, using the division algorithm.

So, let $a=a_0d$, $b=b_0d$. We wish to show that $m=a_0b_0d=\mathrm{lcm}(a,b)$ (so that $md=ab$). As $m=ab_0=a_0b$, it is a common multiple of $a,b$. Let $n=a_1a=b_1b$ be any common multiple of $a,b$. Suppose $r,s$ are integers such that $ra+sb=d$. We have:
$$\begin{array}{rrcl}{} & ra+sb &=& d \\ \implies & ra_0+sb_0 &=& 1 \\ \implies & ra_0(b_1b)+sb_0(a_1a) &=& n \\ \implies & ra_0b_1b_0d+sb_0a_1a_0d &=& n \\ \implies & m(rb_1+sa_1) &=& n\end{array}$$
Thus $m\mid n$, and so $m$ is the lcm of $a,b$ as claimed.

In the OP, $d=1$ and $c$ is a common multiple of $a,b$.