MAT102 Lecture 9

Primes
- $p$ is prime if whenever $p ∣ a b$ then $p ∣ a$ or $p ∣ b$
FTA
- Fundamental Theorem of Arithmetic.
- Unique composition into primes?
Bézout's Identity and other thing:
- if $a m + b n = c$ has a solution $(x_{0}, y_{0})$
- Then the general solution is:
  - $(x_{0} + \frac{b}{gcd (a, b)} k, y_{0} - \frac{a}{gcd (a, b)} k)$
  - Signs must be opposing.
  - $(x_{0} - \frac{b}{gcd (a, b)} k, y_{0} + \frac{a}{gcd (a, b)} k)$

$- 800 + 17 n > 0$
$17 n > 800$
$n > \frac{800}{17}$
$n >\approx 47$
$900 - 19 n > 0$
$- 19 n > - 900$
$19 n < 900$
$\frac{n < 900}{19}$
$n < 47.3$
$47.36 > n > 47.05$
- The solution here wouldn't work, there is no integer where $n$ currently resides, there are only rational solutions here.

$3^{a} \cdot 9^{b} = 3^{c} \cdot 9^{d}$
$3^{a} \cdot 3^{2 b} = 3^{c} \cdot 3^{2 d}$
$3^{a + 2 b} = 3^{c + 2 d}$
$a + 2 b = c + 2 d$
$a + (2 b) = c + (2 d)$
- Exponential functions are injective.
- $f (x) = 3^{x}$
  - One to one function
- $f (x) = f (y) ⟹ x = y$
- $3^{x} = 3^{y}$
- This uses the FTA

If $6 ∣ a b$ then $6 ∣ a$ or $6 ∣ b$
If a prime divides $a b$ , then it divides either $a$ or $b$ .

1
- a
  - $a \in N$
  - $a = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{n}^{a_{n}}$
  - Want to show that if $b \in N$ then $b ∣ a ⟺ b = p_{1}^{d_{1}} p_{2}^{d_{2}} \dots p_{n}^{d_{n}}$
  - $a = b k$ for some $k \in Z$
  - If $b = p_{1}^{b_{1}} p_{2}^{b_{2}} \dots$
  - $a = (p_{1}^{b_{1}} p_{2}^{b_{2}} \dots p_{n}^{b_{n}}) k$
  - $p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{n}^{a_{n}} = (p_{1}^{b_{1}} p_{2}^{b_{2}} \dots p_{n}^{b_{n}}) k$
  - $p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{n}^{a_{n}} = (p_{1}^{b_{1}} p_{2}^{b_{2}} \dots p_{n}^{b_{n}}) (r_{1}^{c_{1}} r_{2}^{c_{2}} \dots r_{m}^{c_{m}})$
  - This means that the prime factorization of $a$ is some multiple of the prime factorization of $b$ .
  - $d_{i} \leq a_{i}$ , this is true because we need to multiply everything in $b$ by $k$ to get $a$ . This can only work if $b \leq a$ .
  - There also must be some other $b_{j}$ for some $j \in R$ where $b_{j} = a_{i}$ .
  - Want to prove that the prime factorization of $b$ are the same as $a$ .
  - Prove that the exponents are smaller for b.
  - $⟹$
    - Supposed $b ∣ a$
    - The prime factors of $b$ are the same as $a$ .
    - Proof
      - Suppose for a contradiction that $q ∣ b$
      - But $q \neq p_{i}$ for any $i$ .
      - Thus $q ∣ a$
      - $a = p_{1}^{a_{1}} \dots p_{n}^{a_{n}}$
      - Thus $q ∣ p_{i}$ for some $i$ .
      - Thus $q = p_{i}$
      - Contradiction.
      - All the prime factors of $b$ are the prime factors of $a$ .
      - $b = p_{1}^{d_{1}} \dots p_{n}^{d_{n}}$ for some $d \in Z$
    - Since $b ∣ a, \exists k \in Z$ such that $a = b k$ since $k ∣ a$ then $k = p_{1}^{e_{1}} \dots p_{n}^{e_{n}}$ . and so $p_{1}^{a_{1}} \dots = a$
    - $p_{1}^{e_{1} + d_{1}}$
    - $a_{i} = e_{i} + d_{i}$
  - $⟸$
    - Suppose $b = p_{1}^{d_{1}}$ let $k = p_{1}^{a_{1} - d_{1}}$
    - $b k = p_{1}^{d_{1}} p_{1}^{a_{1} - d_{1}}$
    - $= p_{1}^{a_{1}} = a$
- b
  - $a, b \in N$
  - $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}}$
  - Want to 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 $a = k d$
  - let $b = j d$ for some $k, j \in Z$ .
  - Let $d_{i} = min (a_{i, b_{i)}})$ so $d_{i} \leq a_{i}$
  - and $d_{i} \leq b_{i}$
  - so $c = p_{1}^{d_{1}}$ satisfied $c ∣ a$ and $c ∣ b$
  - $c$ is a common divisor of $a$ and $b$ .
  - Show that every other divisor divides $c$
  - Let $f = p_{1}^{f_{1}} \dots$ be some other common factor
  - $f_{i} \leq a_{i}$ and $f_{i} \leq b_{i}$
  - if you're less than both, you're less than the min
    - $f_{i} \leq min (a_{i}, b_{i})$