State/Canonical decompositions can be used to find GCD and LCM

From SlugmathWiki

Proposition
Proof

Proposition: (Canonical decompositions can be used to find GCD and LCM.) Suppose that $a,b \in \NN$, and $a,b \neq 0$. Let $(e_p)$ and $(f_p)$ be the exponents occurring in the canonical decomposition of $a$ and $b$ into primes: $$a = \prod_{p \in P} p^{e_p}, \mbox{ and } b = \prod_{p \in P} p^{f_p}.$$ Let $g_p = min(e_p, f_p)$, and let $\ell_p = max(e_p, f_p)$, for all $p \in P$.

Then, the canonical decompositions of $GCD(a,b)$ and $LCM(a,b)$ are: $$GCD(a,b) = \prod_{p \in P} p^{g_p}, \mbox{ and } LCM(a,b) = \prod_{p \in P} p^{\ell_p}.$$

Logical Connections

This statement logically relies on the following definitions and statements: Def/Canonical decomposition into primes, Def/Greatest common divisor, Def/Least common multiple, State/Divisibility corresponds to inequalities of prime exponents

The following statements and definitions rely on the material of this page: State/The GCD times the LCM is the product

To visualize the logical connections between this statements and other items of mathematical knowledge, you can visit the following cluster(s), and click the "Visualize" tab: Clust/Basic number theory

Suppose that $a,b \in \NN$, and $a,b \neq 0$. Let $(e_p)$ and $(f_p)$ be the exponents occurring in the canonical decomposition of $a$ and $b$ into primes:

$$a = \prod_{p \in P} p^{e_p}, \mbox{ and } b = \prod_{p \in P} p^{f_p}.$$ Let $g_p = min(e_p, f_p)$, and let $\ell_p = max(e_p, f_p)$, for all $p \in P$.

Define $g$ and $\ell$ by:

$$g = \prod_{p \in P} p^{g_p}, \mbox{ and } \ell = \prod_{p \in P} p^{\ell_p}.$$ There are two statements to be proven:

$g = GCD(a,b)$

There are two statements that axiomatize the greatest common divisor $GCD(a,b)$, that we prove about $g$.

$g \vert a,b$.	Since $g_p = min(e_p, f_p)$, it follows that $g_p \leq e_p$ and $g_p \leq f_p$, for all $p \in P$. Since divisibility corresponds to inequalities of prime exponents, it follows that $g$ divides both $a$ and $b$.
$g$ maximal.	Suppose that $d \in \NN$ and $d$ divides $a$ and $d$ divides $b$. Let $(d_p)$ be the sequence of exponents in the canonical decomposition of $d$. Then since $d$ divides $a$ and $d$ divides $b$, we find that $d_p \leq e_p$ and $d_p \leq f_p$ for all $p \in P$. Hence $d_p \leq min(e_p, f_p)$, for all $p \in P$. We find that $d$ divides $g$.
Hence $g = GCD(a,b)$.

$\ell = LCM(a,b)$

There are two statements that axiomatize the least common multiple $LCM(a,b)$, that we prove about $\ell$.

$a,b \vert \ell$.	Since $\ell_p = max(e_p, f_p)$, it follows that $\ell_p \geq e_p$ and $\ell_p \geq f_p$, for all $p \in P$. It follows that $a$ divides $\ell$ and $b$ divides $\ell$.
$\ell$ minimal.	Suppose that $m \in \NN$, and $a$ divides $m$ and $b$ divides $m$. Let $(m_p)$ be the sequence of exponents in the canonical decomposition of $m$. Then since $a$ divides $m$ and $b$ divides $m$, we find that $e_p \leq m_p$ and $f_p \leq m_p$. Hence $max(e_p, f_p) \leq m_p$, for all $p \in P$. We find that $\ell$ divides $m$.
Hence $\ell = LCM(a,b)$.

Thus $GCD(a,b)$ and $LCM(a,b)$ can be found using the exponents in the canonical decompositions of $a$ and $b$.

State/Canonical decompositions can be used to find GCD and LCM

From SlugmathWiki

Logical Connections

Views

Personal tools

Navigation

Mathematics

Pegagogy

Search

Toolbox