MAT102 Lecture 10

2
- a
  - $lcm (3, 5)$
  - $gcd (3, 5) = 1$
  - $l c m (3, 5) = 15$
  - $l c m (6, 9)$
  - $gcd (6, 9) = 3$
  - $\frac{6 * 9}{3}$
  - $\frac{54}{3}$
  - $18$
  - $l c m (6, 9) = 18$
  - $l c m (10, 36)$
  - $gcd (10, 36)$
  - ${\begin{cases} 36 = & 10 (3) + 6 \\ 10 = & 6 (1) + 4 \\ 6 = & 4 (1) + 2 \\ 4 = & 2 (2) + 0 \end{cases}$
  - $gcd (10, 36) = 2$
  - $\frac{10 * 36}{2}$
  - $\frac{360}{2}$
  - $180$
  - $l c m (a, b) = \frac{| a b |}{gcd (a, b)}$
- b
  - If $a, b \in Z$ and $a, b \neq 0$ .
  - Then show $\frac{a b}{gcd (a, b)}$ exists.
  - The well-ordering principle states that we must have a minimal element in a non-empty set.
  - Is the least common multiple part of a set?
    - Maybe $Z$ ?
  - We can have the $gcd (a, b) = d$
  - This means that $d ∣ a$ and that $d ∣ b$
  - We can rewrite that as:
    - $a = d k$ for some $k \in Z$
    - $b = d j$ for some $j \in Z$
  - This means that we have $\frac{(d k) (d j)}{d}$ as the definition for the $l c m (a, b)$
  - $\frac{d k d j}{d}$
  - $\frac{d^{2} k j}{d}$
  - $\frac{d (d k j)}{d (1)}$
  - $d k j \in Z$ since $d, k, j \in Z$ beforehand.
  - This means $a j$ or $b k$ . This tells us that we can multiply each number by the $gcd$ and the integer for the other number.
  - $a j, b k \in Z$ , which also shows us that there are integer solutions for the least common multiple.
  - If $a j, b k \in Z$ that means there is a least element?
  - Assume $a, b > 0$
  - Let $S = {d \in N : a ∣ d, b ∣ d}$
    - This is a set of common multiples for $a, b$
    - let $a b \in S$
    - $S \neq \emptyset$
  - By the well ordering principle, $S$ has a least element, which is the $l c m$ .
- c
  - Suppose $a$ and $b$ are natural numbers. Using a common set of distinct primes, $p_{1}, \dots, p_{n}$ , write $a$ and $b$ as:
    - $a = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{n}^{a_{n}}$
    - $b = p_{1}^{b_{1}} p_{2}^{b_{2}} \dots p_{n}^{b_{n}}$
  - Where some of the $a_{i}$ and $b_{i}$ may be zero as necessary.
  - Show that:
    - $l c m (a, b) = p_{1}^{max (a_{1}, b_{1})} p_{2}^{max (a_{2}, b_{2})} \dots p_{n}^{max (a_{n}, b_{n})}$
  - Let $d_{i} = max (a_{i}, b_{i})$ and set $d = p_{1}^{d_{1}} p_{2}^{d_{2}} \dots p_{n}^{d_{n}}$ .
  - Claim $d$ is a common multiple of $a, b$
    - Show that $a ∣ d$ and $b ∣ d$
      - Note that $a_{i} \leq max (a_{i}, b_{i}) = d_{i}$
      - $b_{i} \leq d_{i}$
    - By (1)a from this week that says:
      - $a ∣ d$ and $b ∣ d$ .
  - Claim $d$ is the least common multiple.
    - Show that it divides every other common multiple.
    - If $c$ is another common multiple, then $d ∣ c$ , and so $d \leq c$ .
    - Let $c = p_{1}^{c_{1}} p_{2}^{c_{2}} \dots p_{n}^{c_{n}} q_{1}^{k_{1}} q_{2}^{k_{2}} \dots q_{n}^{k_{n}}$
    - Since $a ∣ c$ and $b ∣ c$ , that means $a_{i} \leq c_{i}$ and $b_{i} \leq c_{i}$
    - So $max (a_{i}, b_{i}) \leq c_{i}$
    - Therefore $d ∣ c$ .
  - $l c m (a, b) = p_{1}^{d_{1}} p_{2}^{d_{2}} \dots p_{n}^{d_{n}} q_{1}^{0} q_{2}^{0} \dots q_{n}^{0}$
  - $l c m (a, b) = p_{1}^{d_{1}} p_{2}^{d_{2}} \dots p_{n}^{d_{n}} q_{1}^{k_{1}} q_{2}^{k_{2}} \dots q_{n}^{k_{n}}$