Welcome to our community

Be a part of something great, join today!

Number Theory j1.1.6 Suppose a and b are integers that divide the integer c

karush

Well-known member
Jan 31, 2012
2,861
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:confused:
 
Last edited by a moderator:

Greg

Perseverance
Staff member
Feb 5, 2013
1,401
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
Jan 31, 2012
2,861
so the $\vert$ means factor of
 

Olinguito

Well-known member
Apr 22, 2018
251
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
Feb 5, 2013
1,401

Olinguito

Well-known member
Apr 22, 2018
251
By the way the second line of the OP should read $ab\mid c$.
 

karush

Well-known member
Jan 31, 2012
2,861

Olinguito

Well-known member
Apr 22, 2018
251
yeah saw that
but too late to change

but mahalo
ʻAʻole pilikia. (Wave)

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