↑
- MAT102 Final Exam Prep

MAT102 Worksheet 5 Review

Q1

A

Let $a \in N$ and write $a$ in terms of it's prime factorization. $a = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{n}^{a_{n}}$ where $p_{1}, p_{2}, \dots, p_{n}$ are distinct primes.
Show that $b \in N$ divides $a ⟺ b$ has a prime factorization $p_{1}^{d_{1}} p_{2}^{d_{2}} \dots p_{n}^{d_{n}}$ where $0 \leq d_{i} \leq a_{i}$ for $i = 1, \dots, n$ .
We want to show that $b ∣ a ⟺ p_{1}^{d_{1}} p_{2}^{d_{2}} \dots p_{n}^{d_{n}} \leq p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{n}^{a_{n}}$
$⟹$
- $b ∣ a$
- This means that $a = b k$ for some $k \in Z$
- However if we show it in the form of prime factorization notice that we get:
  - $p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{n}^{a_{n}} = (p_{1}^{d_{1}} p_{2}^{d_{2}} \dots p_{n}^{d_{n}}) (p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{n}^{k_{n}})$ where $p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{n}^{k_{n}} = k$
- Because we have the same primes, but different exponents, we equate them.
- $a_{1}, \dots, a_{n} = (d_{1}, \dots, d_{n}) + (k_{1}, \dots, k_{n})$
- For ease of writing let's use $a_{i}, d_{i}$ and $k_{i}$
- $a_{i} = d_{i} + k_{i}$
- If we isolate $d_{i}$ we get that $d_{i} = a_{i} - k_{i}$
- This clearly shows that $d_{i} \leq a_{i}$ for $k_{i}$ being either $0$ or positive.
$⟸$
- We know that $0 \leq d_{i} \leq a_{i}$
- $b = p_{1}^{d_{1}} p_{2}^{d_{2}} \dots p_{n}^{d_{n}}$
- So the primes of $a = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{n}^{a_{n}}$
- Let's show that $b ∣ a$
- So $a = b k$ for some $k \in Z$
- $p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{n}^{a_{n}} = (p_{1}^{d_{1}} p_{2}^{d_{2}} \dots p_{n}^{d_{n}}) (k)$
- Let $k = p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{n}^{k_{n}}$
- So $p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{n}^{a_{n}} = (p_{1}^{d_{1}} p_{2}^{d_{2}} \dots p_{n}^{d_{n}}) (p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{n}^{k_{n}})$
- This shows us that $a_{i} = d_{1} + k_{i}$
- This shows us divisibility.

B

Suppose that $a$ and $b$ are natural numbers. Using a common set of prime numbers:
- $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 $a_{i}$ and $b_{i}$ are zero as necessary.
Show that $gcd (a, b) = p_{1}^{min (a_{1}, b_{1})} p_{2}^{min (a_{2}, b_{2})} \dots p_{n}^{min (a_{n}, b_{n})}$
$⟹$
- Let the $gcd (a, b) = d$
- As an example we know that $b ∣ a$ then $a, b$ have the same set of primes, and that $b_{i} \leq a_{i}$ . (These $a, b$ do not refer to the $a, b$ in this question).
- So we can assume that $d$ has the same set of primes, but different exponents.
- So let $d = p_{1}^{d_{1}} p_{2}^{d_{2}} \dots p_{n}^{d_{n}}$
- If we have $gcd (a, b) = d$ then $d ∣ a$ and $d ∣ b$
- So:
  - $p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{n}^{a_{n}} = (p_{1}^{d_{1}} p_{2}^{d_{2}} \dots p_{n}^{d_{n}}) (p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{n}^{k_{n}})$ where $k = p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{n}^{k_{n}}$ and $k \in Z$
  - Notice that $a_{i} = d_{i} + k_{i}$
  - $p_{1}^{b_{1}} p_{2}^{b_{2}} \dots p_{n}^{b_{n}} = (p_{1}^{d_{1}} p_{2}^{d_{2}} \dots p_{n}^{d_{n}}) (p_{1}^{j_{1}} p_{2}^{j_{2}} \dots p_{n}^{j_{n}})$ where $j = p_{1}^{j_{1}} p_{2}^{j_{2}} \dots p_{n}^{j_{n}}$ and $j \in Z$
  - Notice that $b_{i} = d_{i} + j_{i}$
  - $d_{i} = a_{i} - k_{i}$
  - $d_{i} = b_{i} - j_{i}$
  - $d_{i} + k_{i} = a_{i}$
  - $d_{i} + j_{i} = b_{i}$
  - Notice that to reach either $a$ or $b$ , we multiply $d$ by $k$ or $j$ to get to our number.
  - In order to be the $gcd (a, b) = d$ then $d_{i} \leq a_{i}$ and $d_{i} \leq b_{i}$
  - Notice that with $d_{i} + k_{i} = a_{i}$ it shows that it's less than $a_{i}$ , so $d ∣ a$
  - Notice with $d_{i} + j_{i} = b_{i}$ it shows that it's less than $b_{i}$ so $d ∣ b$ .
  - So in order to divide both, $(d_{i} \leq a_{i}) \land (d_{i} \leq b_{i})$
  - So to fulfill this, $d_{i} = min (a_{i}, b_{i})$ , because then no matter what, $d_{i}$ will be less than or equal to both $a_{i}$ and $b_{i}$
- So we get that $p_{1}^{d_{1}} p_{2}^{d_{2}} \dots p_{n}^{d_{n}} = p_{1}^{min (a_{1}, b_{1})} p_{2}^{min (a_{2}, b_{2})} \dots p_{n}^{min (a_{n}, b_{n})}$
- This proves that $gcd (a, b) = p_{1}^{min (a_{1}, b_{1})} p_{2}^{min (a_{2}, b_{2})} \dots p_{n}^{min (a_{n}, b_{n})}$ as required.

C

Determine the $gcd (a, b)$ where $a = 9^{4} \cdot 10^{2}$ and $b = 12^{3}$
- $a = 656100$ and $b = 1728$
Let's proceed with the euclidean algorithm.
${\begin{cases} 656100 & = 1728 (379) + 1188 \\ 1728 & = 379 (4) + 212 \\ 379 & = 212 (1) + 167 \\ 212 & = 167 (1) + 45 \\ 167 & = 45 (3) + 32 \\ 45 & = 32 (1) + 13 \\ 32 & = 13 (2) + 6 \\ 13 & = 6 (2) + 1 \\ 6 & = 1 (6) + 0 \end{cases}$
The $gcd (a, b) = 6$
Now doing this with prime factorization:
- $a = 9^{4} \cdot 10^{2}$
- $a = (3^{2})^{4} \cdot (2 \cdot 5)^{2}$
- $a = 3^{8} \cdot 2^{2} \cdot 5^{2}$
- $b = 12^{3}$
- $b = (6 \cdot 2)^{3}$
- $b = (3 \cdot 2 \cdot 2)^{3}$
- $b = 3^{3} \cdot 2^{3} \cdot 2^{3}$
- $b = 3^{3} \cdot 2^{6}$
Now we know that $gcd (a, b) =$ the same set of primes with the minimal exponent.
So what's the only prime that shows in both, and we take the smaller exponent.
We see $3$ and $2$
We see $2^{2}$ as the smallest and $3^{3}$ as the smallest
So we can take $2^{2} \cdot 3^{3}$ as our $gcd (a, b)$
$gcd (a, b) = 108$
This is different than what was calculated with the eucliedean algorithm, this is correct, the eucliedean algorithm was not.

Q2

If $a, b \in Z$ , we say $c$ is a common multiple of $a, b$ if $a ∣ c$ and $b ∣ c$ . The least common multiple of $a$ and $b$ is $lcm (a, b)$ . This is the smallest positive integer divisible by both $a$ and $b$ .

A

$lcm (3, 5)$
- $3 \cdot 5 = 15$
$lcm (6, 9)$
- $gcd (6, 9) = 3$
- $\frac{6 \cdot 9}{3}$
- $18$
$lcm (10, 36)$
- $10 = 2 \cdot 5$
- $36 =$
  - $18 \cdot 2$
  - $9 \cdot 2 \cdot 2$
  - $3^{2} \cdot 2 \cdot 2$
  - $3^{2} \cdot 2^{2}$
- $gcd (10, 36) = 2$
- $lcm (10, 36) = \frac{10 \cdot 36}{2}$
- $lcm (10, 36) = 180$

B

Prove that if $a, b$ are natural numbers, then their $lcm$ exists.
Notice the pattern above
We know that the $gcd (a, b)$ exists
$a \cdot b$ exists if $a, b \in R$ , this is true because $N \subseteq R$ .
This means we inherit field axioms from $R$ such has closure of multiplication.
This proves that $a \cdot b$ exists.
so then we take $\frac{a \cdot b}{| gcd (a, b) |}$
the $| gcd (a, b) |$ takes care of the case in case $a \cdot b < 0$ .

C

Suppose that $a$ and $b$ are natural numbers, using a common set of distinct primes $p_{1}, \dots, p_{n}$ write $a, 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 $a_{i}, b_{i}$ may be zero as necessary.
Show that $lcm (a, b) = p_{1}^{max (a_{1}, b_{1})} p_{2}^{max (a_{2}, b_{2})} \dots p_{n}^{max (a_{n}, b_{n})}$
We know that $lcm (a, b) = \frac{a \cdot b}{| gcd (a, b) |}$
Let $lcm (a, b) = c$
Because $\frac{a \cdot b}{| gcd (a, b) |}$ $a \cdot b$ will result in the same set of primes, $gcd (a, b)$ also has the same set of primes. So we can assume that $c = p_{1}^{c_{1}} p_{2}^{c_{2}} \dots p_{n}^{c_{n}}$
let $| gcd (a, b) | = p_{1}^{d_{1}} p_{2}^{d_{2}} \dots p_{n}^{d_{n}}$
$a \cdot b = p_{1}^{a_{1} + b_{1}} p_{2}^{a_{2} + b_{2}} \dots p_{n}^{a_{n} + b_{n}}$
So we have $\frac{p_{1}^{a_{1} + b_{1}} p_{2}^{a_{2} + b_{2}} \dots p_{n}^{a_{n} + b_{n}}}{p_{1}^{d_{1}} p_{2}^{d_{2}} \dots p_{n}^{d_{n}}}$
Now we have that $p_{1}^{a_{1} + b_{1} - d_{1}} p_{2}^{a_{2} + b_{2} - d_{2}} \dots p_{n}^{a_{n} + b_{n} - d_{n}}$
We already know from previous weeks in the course that $gcd (a, b) = p_{1}^{min (a_{1}, b_{2})} p_{2}^{min (a_{2}, b_{2})} \dots p_{n}^{min (a_{n}, b_{n})}$
$p_{1}^{a_{1} + b_{1} - min (a_{1}, b_{1})} p_{2}^{a_{2} + b_{2} - min (a_{2}, b_{2})} \dots p_{n}^{a_{n} + b_{n} - min (a_{n}, b_{n})}$
What this means is if:
- Case 1: $a_{i}$ is smaller
  - This is essentially $a_{1} + b_{1} - a_{1}$ which is $b_{1}$
  - So it's the opposite of the $min (a, b)$ which we can call the $max (a, b)$ as there are only two numbers being compared
- Case 2: $b_{i}$ is smaller
  - This is $a_{1} + b_{1} - b_{1}$ which is $a_{1}$
  - Same logic, this chooses the opposite of the minimum.
So this essentially means that we get $p_{1}^{max (a_{1}, b_{1})} p_{2}^{max (a_{2}, b_{2})} \dots p_{n}^{max (a_{n}, b_{n})}$