MAT102 Lecture 16B

08NumberTheoryIIExercises_Students.pdf

Find the $gcd (252, 105)$
$gcd (252, 105) = gcd (105, 42) = gcd (42, 21) = 21$
Prime factorize $105$
- $105 = 3 \cdot 5 \cdot 7$
- $252 = 2^{2} 3^{2} 7$
- Get a common prime factor
- $105 = 2^{0} 3^{1} 5^{1} 7^{1}$
- Divisors of $105$
  - ${1, 3, 5, 7, \underset{3 \cdot 5}{\underset{⏟}{15}}, \underset{3 \cdot 7}{\underset{⏟}{21}}, \underset{5 \cdot 7}{\underset{⏟}{35}}, \underset{3 \cdot 5 \cdot 7}{\underset{⏟}{105}}}$
- $252 = 2^{2} 3^{2} 5^{0} 7^{1}$
  - $3$ ways of having $2^{x}$
  - $3$ ways of having $3^{x}$
  - $0$ ways of having $5^{x}$
  - $2$ ways of having $7^{x}$
  - $(3) (3) (2) = 18$ possible combinations
- Every prime is a factor of its factorization
- $gcd (252, 105) = 2^{0} 3^{1} 5^{0} 7^{1} = 21$
Let $a, b \in Z$ be written with common primes $p_{1} - p_{n}$ as:
- $a = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{n}^{a_{n}}$
- and $b = p_{1}^{b_{1}} p_{2}^{b_{2}} \dots p_{n}^{b_{n}}$
- Then $a ∣ b ⟺ a_{i} \leq b_{i}$ for all $i = b$
- $⟸$
  - If $a_{i} \leq b_{i}$ for all $i = 1, \dots, n$
  - $a_{1} a_{2} \dots a_{n} \leq b_{1} b_{2} \dots b_{n}$
  - So $p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{n}^{a_{n}} \leq p_{1}^{b_{1}} p_{2}^{b_{2}} \dots p_{n}^{b_{n}}$
  - To show that $a ∣ b$ we need to show that $a k = b$
  - So $a_{i} + k_{i} = b_{i}$ since $a_{i} \leq b_{i}$
    - This is because with exponents addition is with multiplication like: $a^{r} a^{d} = a^{r + d}$ not $a^{r d}$
    - $(a^{r})^{d}$
  - This means that $p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{n}^{a_{n}} p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{n}^{k_{n}} = p_{1}^{b_{1}} p_{2}^{b_{2}} \dots p_{n}^{b_{n}}$
    - This uses monotonicity of primes, which we haven't proven yet.
    - Saying that $a_{i} \leq b_{i} ⟹ p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{n}^{a_{n}} \leq p_{1}^{b_{1}} p_{2}^{b_{2}} \dots p_{n}^{b_{n}}$
  - Since $a = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{n}^{a_{n}}$ and $b = p_{1}^{b_{1}} p_{2}^{b_{2}} \dots p_{n}^{b_{n}}$ and $k = p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{n}^{k_{n}}$
  - Then we have $a k = b$
  - Proven
  - Solution:
    - Suppose $a_{i} \leq b_{i}$ for all $i$
    - Example:
      - See that $2 \cdot 3 \cdot 7 ∣ 2^{3} 3^{5} 7^{4}$
      - Our needed exponents are $2^{2} 3^{4} 7^{3}$
    - Suppose that $a_{i} + r_{i} = b_{i}$
    - Sub this into $b$
    - $b = p_{1}^{b_{1}} p_{2}^{b_{2}} \dots p_{n}^{b_{n}}$
    - $b = p_{1}^{a_{1} + r_{1}} p_{2}^{a_{2} + r_{2}} \dots p_{n}^{a_{n} + r_{n}}$
    - $b = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{n}^{a_{n}} p_{1}^{r_{1}} p_{2}^{r_{2}} \dots p_{n}^{r_{n}}$
    - See that $a = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{n}^{a_{n}}$
    - so $b = a (p_{1}^{r_{1}} p_{2}^{r_{2}} \dots p_{n}^{r_{n}})$
- $⟹$
  - $a ∣ b$
  - Want to show that $a_{i} \leq b_{i}$ for all $i \in N$
  - $a ∣ b ⟹ a k = b$ for some $k \in Z$
  - We know that $a = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{n}^{a_{n}}$ and $b = p_{1}^{b_{1}} p_{2}^{b_{2}} \dots p_{n}^{b_{n}}$
  - Since b is a times something, we don't know that the something can be written as the same prime factorization
  - So we need to prove: if $a k = b$ then $k \cdot p_{1}^{r_{1}} \dots p_{n}^{r_{n}}$
    - So there can't be another prime that shows up in the factorization of $k$
    - Suppose there is a different prime $q$ that shows up in $k$ , then you can conclude it's a factor of $b$ then $q ∣ a k$ and $q ∣ b$
    - So $q$ must be in the factorization of $b$ which is a contradiction
      - This is by the fta
  - $a k = b ⟹ k \cdot p_{1}^{r_{1}} p_{2}^{r_{2}} \dots p_{n}^{r_{n}}$
    - $a k = b$
    - Suppose there's another prime $q$ which divides $b$ and $a$ which has the same factors as $k = q_{1}^{k_{1}} q_{2}^{k_{2}} \dots q_{n}^{k_{n}}$
    - $q = q_{1}^{a_{1}} q_{2}^{a_{2}} \dots q_{n}^{a_{n}}$
    - $q ∣ b$
    - Which means that $b = q_{1}^{b_{1}} q_{2}^{b_{2}} \dots q_{n}^{b_{n}}$ and $a = q_{1}^{a_{1}} q_{2}^{a_{2}} \dots q_{n}^{a_{n}}$
    - Which is a contradiction considering we know that $b$ is already $= p_{1}^{b_{1}} p_{2}^{b_{2}} \dots p_{n}^{b_{n}}$
    - So this shows a contradiction.
    - So $k$ has the same prime factors as $b$
    - So $k = p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{n}^{k_{n}}$
Suppose $a$ and $b$ are natural numbers
Using a set of primes:
- $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}}$
Show that $gcd (a, b) = p_{1}^{m i n (a_{1}, b_{1})} p_{2}^{m i n (a_{2}, b_{2})} \dots p_{n}^{m i n (a_{n}, b_{n})}$
- Let $gcd (a, b) = d$
- Suppose that $d$ has the same prime factors as $a$ and $b$ .
- This means that $d_{i} \leq a_{i}$ and $d_{i} \leq b_{i}$ as $min (a_{i}, b_{i}) \leq a_{i}$ and $min (a_{i}, b_{i}) \leq b_{i}$
- So $d ∣ a$ and $d ∣ b$
- To show it's the greatest common divisor:
  - Proposition that $d$ is the greatest common divisor $⟺$ all other common divisors divide $d$
  - Suppose $d$ is the greatest common divisor
  - Let $q_{i} = {p_{1}^{q_{1 a}} p_{2}^{q_{2 a}} \dots p_{n}^{q_{a n}}, p_{1}^{q_{1 b}} p_{2}^{q_{2 b}} \dots p_{n}^{q_{n b}}, \dots}$
  - For $i = a, b, c, \dots$
  - $q_{i} + k_{i} = d_{i}$
- Solution:
  - To prove it's a common divisor:
    - $min (a_{i}, b_{i}) \leq a_{i}$
    - $min (a_{i}, b_{i}) \leq b_{i}$
    - So by the lemma, $p_{1}^{m i n (a_{1}, b_{1})} p_{2}^{m i n (a_{2}, b_{2})} \dots p_{n}^{m i n (a_{n}, b_{n})} ∣ a$ and $p_{1}^{m i n (a_{1}, b_{1})} p_{2}^{m i n (a_{2}, b_{2})} \dots p_{n}^{m i n (a_{n}, b_{n})} ∣ b$
  - To prove it's the greatest common divisor:
    - If $c ∣ a$ and $c ∣ b$ , then $c ∣ p_{1}^{m i n (a_{1}, b_{1})} p_{2}^{m i n (a_{2}, b_{2})} \dots p_{n}^{m i n (a_{n}, b_{n})}$
    - Write $c$ as a prime factorization:
      - $c = p_{1}^{c_{1}} p_{2}^{c_{2}} \dots p_{n}^{c_{n}}$
      - Since $c ∣ a$ it must have the same primes as $a$ , the same applies to $b$
      - Now suppose that $c ∣ a$ and $c ∣ b$
      - By the lemma, this means that $c_{i} \leq a_{i}$ and $c_{i} \leq b_{i}$ for all $i = 1, \dots, n$
      - So $c_{i} \leq min (a_{i}, b_{i})$
      - So $c ∣ p_{1}^{m i n (a_{1}, b_{1})} p_{2}^{m i n (a_{2}, b_{2})} \dots p_{n}^{m i n (a_{n}, b_{n})}$
Find all solutions to the linear diophantine: $1260 x + 232 y = 16$
- Euclidean algorithm
- ${\begin{cases} 1260 & = 232 (5) + 100 \\ 232 & = 100 (2) + 32 \\ 100 & = 32 (3) + 4 \\ 32 & = 4 (8) + 0 \end{cases}$
- See that the $gcd (1260, 232) = 4$
- $1260 x + 232 y = 16$
- $1260 x + 232 y = 4 (4)$
- $(100 + 32 (- 3)) (4) = 4 (4)$
- $((1260 + 232 (- 5)) + (232 + 100 (- 2)) (- 3)) (4) = 4 (4)$
- $(1260 + 232 (- 5) + (232 + 100 (- 2)) (- 3)) (4) = 4 (4)$
- $(1260 + 232 (- 5) + 232 (- 3) + 100 (6)) (4) = 4 (4)$
- $1260 (4) + 232 (- 5) (4) + 232 (- 3) (4) + 100 (6) (4) = 4 (4)$
- $1260 (4) + 232 (- 20) + 232 (- 12) + 100 (24) = 4 (4)$
- $1260 (4) + 232 (- 32) + 100 (24) = 4 (4)$
- $1260 (4) + 232 (- 32) + (1260 + 232 (- 5)) (24) = 4 (4)$
- $1260 (4) + 232 (- 32) + 1260 (24) + 232 (- 5) (24) = 4 (4)$
- $1260 (4 + 24) + 232 (- 32 + (- 5) (24)) = 4 (4)$
- $1260 (28) + 232 (- 152) = 16$
- $x = x_{0} + \frac{b}{d} n$
- $x = 28 + \frac{232}{4} n$
- $x = 28 + 58 n$
- $y = y_{0} - \frac{a}{d} n$
- $y = - 152 - \frac{1260}{4} n$
- $y = - 152 - 315 n$