MAT102 Tutorial W10B

Readings 8:
- Exercise 5:
  - $a, b, c \in Z$
  - $a x + b y = c$ has a solution $⟺$ the $gcd (a, b) ∣ c$
  - $⟸$
    - $a x + b y = c$ has a solution
    - $a x_{0} + b y_{0} = c$
    - $gcd (a, b) ∣ c$
    - $gcd (a, b) = d$
    - $d ∣ c$
    - $d k = c$ for some $k \in Z$
    - We know that $a x + b y = gcd (a, b)$
    - So when we multiply by $k$
    - $k a x + k b y = k gcd (a, b)$
    - Let $x_{0} = k x$ and $y_{0} = k y$
    - $a x_{0} + b y_{0} = k gcd (a, b)$
    - $a x_{0} + b y_{0} = d k$
    - We know that $d k$ is $c$
    - $a x_{0} + b y_{0} = c$
  - $⟹$
    - $a x_{0} + b y_{0} = c$
    - Show that $gcd (a, b) ∣ c$
    - $d k = c$ for some $k \in Z$
    - $a x_{1} + b y_{1} = gcd (a, b)$
    - $d ∣ a$ and $d ∣ b$
    - $d ℓ = a$
    - $d j = b$
    - $d l x_{0} + d j y_{0} = c$
    - Let $k = l x_{0} + j y_{0}$
    - $d (l x_{0} + j y_{0}) = c$
    - $d k = c$
    - So it's proven
- Exercise 3a:
  - $a = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{n}^{a_{n}}$
  - $b \in N$
  - $b ∣ a ⟺ b = p_{1}^{d_{1}} p_{2}^{d_{2}} \dots p_{n}^{d_{n}}$ and $0 \leq b_{i} \leq a_{i}$
  - $⟹$
    - $b ∣ a$
    - $b k = a$
    - $b k = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{n}^{a_{n}}$
    - Suppose $b$ has the same prime factorization as $a$ with the exponents being $0$ as necesary
      - $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}}$
      - Let $k = 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}} p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{n}^{k_{n}} = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{n}^{a_{n}}$
      - $p_{1}^{b_{1} + k_{1}} p_{2}^{b_{2} + k_{2}} \dots p_{n}^{b_{n} + k_{n}} = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{n}^{a_{n}}$
      - So $b_{i} + k_{i} = a_{i}$
      - Which shows that $b ∣ a$ if it has the same prime factorization. As $b_{i} \leq a_{i}$
    - Suppose for contradiction that $b$ has a different set of primes as $b = q_{1}^{b_{1}} q_{2}^{b_{2}} \dots q_{n}^{b_{n}}$
      - $q_{1}^{b_{1}} q_{2}^{b_{2}} \dots q_{n}^{b_{n}} p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{n}^{k_{n}} = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{n}^{a_{n}}$
      - $(q_{1}^{b_{1}} p_{1}^{k_{1}}) (q_{2}^{b_{2}} p_{2}^{k_{2}}) \dots (q_{n}^{b_{n}} p_{n}^{k_{n}}) = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{n}^{a_{n}}$
      - This means that the set of primes are the same, however that's a contradiction as we said it had different primes.