Prime Factorisation

Using the fundamental theorem of arithmetic, write natural numbers $a, b$ in the form

$\displaystyle a = \prod_{i=1}^n p_i^{\alpha_i},\quad b = \prod_{i=1}^n p_i^{\beta_i}$

for primes $p_i$ and non-negative indices $\alpha_i, \beta_i$ .

Definition 1. Write $d = \gcd(a, b)$ if it satisfies the following properties:

$d \mid a$ and $d \mid b$ ,
if $c \mid a$ and $c \mid b$ , then $c \leq d$ .

Problem 1. Prove that if $c \mid a$ and $c \mid b$ , then $c \mid \gcd(a, b)$ .

(Click for Solution)

Solution. Since $c \leq \gcd(a, b)$ , by the division algorithm, find unique integers $q,r$ such that

$\gcd(a, b) = q \cdot c + r,\quad 0 \leq r < \gcd(a,b).$

We observe that $r \mid a$ and $r \mid b$ . Therefore, $(\gcd(a,b) + r) \mid a$ and $(\gcd(a, b) + r) \mid b$ . Hence,

$\gcd(a,b) \leq \gcd(a,b) + r \leq \gcd(a, b) \quad \Rightarrow \quad r = 0.$

Hence, $c \mid \gcd(a,b)$ .

Problem 2. Prove that $\gcd(a, b) = \prod_{i=1}^n p_i^{\min\{ \alpha_i, \beta_i\} }$ .

(Click for Solution)

Solution. Denoting the right-hand side by $d$ , it is clear that $d \mid a$ and $d \mid b$ so that by Problem 1, $d \mid \gcd(a, b)$ . On the other hand, use the fundamental theorem of arithmetic to find non-negative indices $\gamma_i$ such that

$\displaystyle \gcd(a,b) = \prod_{i=1}^n p_i^{\gamma_i}.$

If there exists $i$ such that $\gamma_i > \alpha_i$ , then $\gcd(a,b) \nmid a$ , a blatant contradiction. Therefore, $\gamma_i \leq \alpha_i$ for any $i$ . Similarly, $\gamma_i \leq \beta_i$ . Therefore, $\gamma_i \leq \min \{\alpha_i,\beta_i\}$ , so that $\gcd(a,b) \mid d$ . Therefore, $\gcd(a,b) = d$ .

Definition 2. Write $m = \mathrm{lcm}(a, b)$ if it satisfies the following properties:

$a \mid m$ and $b \mid m$ ,
for $n > 0$ , if $a \mid n$ and $b \mid n$ , then $m \leq n$ .

Problem 3. Prove that $\gcd(a,b) \cdot \mathrm{lcm}(a,b) = a \cdot b$ . Deduce that

$\displaystyle \mathrm{lcm}(a,b) = \prod_{i=1}^n p_i^{\max\{ \alpha_i, \beta_i\} }.$

(Click for Solution)

Solution. Define $m := (a \cdot b)/{\gcd(a,b)}$ . It is obvious that $a \mid m$ and $b \mid m$ . By definition,

$\displaystyle \mathrm{lcm}(a,b) \leq m = \frac{a \cdot b}{\gcd(a,b)}\quad \Rightarrow \quad a \cdot b \geq \gcd(a,b) \cdot \mathrm{lcm}(a,b).$

Use the division algorithm to obtain unique integers $q \geq 0, r$ such that

$a \cdot b = q \cdot \mathrm{lcm}(a,b) + r,\quad 0 \leq r < \mathrm{lcm}(a,b).$

We observe that $r = a \cdot b - q \cdot \mathrm{lcm}(a,b)$ so that $a \mid r$ and $b \mid r$ . If $r > 0$ , then $r < \mathrm{lcm}(a, b)$ , a contradiction. Hence $r = 0$ , yielding

$\displaystyle a \cdot b = q \cdot \mathrm{lcm}(a,b) \quad \Rightarrow \quad q = \frac{a \cdot b}{\mathrm{lcm}(a,b)} = \frac{a}{\mathrm{lcm}(a,b)/b} = \frac{b}{\mathrm{lcm}(a,b)/a}.$

We observe that $q \mid a$ and $q \mid b$ so that

$q \leq \gcd(a,b)\quad \Rightarrow\quad a \cdot b \leq \gcd(a,b) \cdot \mathrm{lcm}(a,b).$

Piecing the bounds,

$\displaystyle a \cdot b = \gcd(a,b) \cdot \mathrm{lcm}(a,b).$

Taking advantage of the identity $\min\{x,y\} + \max\{x,y\} = x+y$ , using Problem 2,

$\begin{aligned} \mathrm{lcm}(a,b) &= \frac{a \cdot b}{\gcd(a,b)} = \frac{\prod_{i=1}^n p_i^{\alpha_i} \cdot \prod_{i=1}^n p_i^{\beta_i}}{\prod_{i=1}^n p_i^{\min\{ \alpha_i, \beta_i\} }} \\ &= \prod_{i=1}^n p_i^{(\alpha_i + \beta_i) - \min\{ \alpha_i, \beta_i\} } = \prod_{i=1}^n p_i^{\max\{ \alpha_i, \beta_i\} }. \end{aligned}$

—Joel Kindiak, 18 Sept 25, 1445H

KindiakMath

Prime Factorisation

Leave a comment Cancel reply

Prime Factorisation

Share this:

Leave a comment Cancel reply