MAT102 Test 2 Prep

Worksheet 04

1)

• Show that $x^3+2y^3=4z^3$ has no positive integer solutions. Assume that a solution $(x_0,y_0,z_0)$ of positive integers does exist.
  • a) Argue that $x_0$ must be even
    • The definition for an even number is $a=2k:k\in \mathbb{Z}$.
    • So $x_0=2k$ for some $k\in \mathbb{Z}$.
    • $(2k{)}^3+2y_0^3=4z_0^3$
    • Then we get:
      • $(2k)(2k)(2k)$
      • $4k^2(2k)$
      • $8k^3$
    • $8k^3+2y_0^3=4z_0^3$
    • We can factor out two from the whole equation:
    • $2(4k^3+y_0^3=2z_0^3)$
    • Gives us:
      • $4k^3+y_0^3=2z_0^3$
      • This means that all $(x_0,y_0,z_0)$ are even, as when we substitute the evenness definition into $y_0$ and $z_0$, we could keep on factoring $2$ out.

    ---

    • Thinking framework:
      • Show that $x_0$ can be expressed as $2(\text{something})$
    • $x_0^3=4z_0^3-2y_0^3$
    • $x_0^3=2(2z_0^3-y_0^3)$
  • b)
    • The above where we keep re-expressing either $(x_0,y_0,z_0)$ as an even.
  • c)
    • Let's have $x_0,y_0,z_0$ be the solutions.
    • Let's express every one of these as their even definitions.
    • We know from the above that all are even so,
    • $x_0=2x_1$
    • $y_0=2y_1$
    • $z_0=2z_1$
    • $(2x_1{)}^3+2(2y_1{)}^3=4(2z_1{)}^3$
      • $(2x_1{)}^3$
      • $(2x_1)(2x_1)(2x_1)$
      • $(4x_1^2)(2x_1)$
      • $(8x_1^3)$
    • $8x_1^3+16y_1^3=32z_1^3$
    • Factor out 8
    • $8(x_1^3+2y_1^3=4z_1^3)$
    • $x_1^3+2y_1^3=4z_1^3$
    • Now we get that $x_1,y_1,z_1$ are solutions, we know that $x_1,y_1,z_1$ are larger than $x_0,y_0,z_0$ because of the evenness definition.
  • d)
    • This is a contradiction because there are no positive solutions. But we found one assuming there are solutions. This can repeat infinitely. This models the proof of 'there isn't a smallest positive real number', where we can keep finding a smaller positive real number, telling us that there isn't one. This is the same idea here.
• • a) Show that the equation $ax+by=c$ has a solution if and only if $gcd(a,b)\mid c$
    • Let's set the $gcd(a,b)=d$
    • so $d\mid c$ which means $c$ can be rewritten as $c=ad$ for some $a\in \mathbb{Z}$.
    • We also know that $gcd(a,b)$ means that $d\mid a$ and $d\mid b$.
      • So:
      • $a=gd$
      • $b=hd$
      • for some $g,h\in \mathbb{Z}$.
    • $⟹$Let's modulate the first equation to get the second.
      • $ax+by=c$
      • $gd(x)+hd(y)=c$
      • $d(gx)+d(hy)=c$
      • $d(gx+hy)=c$
      • If $gx$ and $hy$ are $\in \mathbb{Z}$, (which they are). Then we can re-express $gx+hy=d_1$
      • So now $c=d{d}_1$, which is essentially the same as $c=ad$.
    • $⟸$We now have to modulate $c=ad$ to reach $ax+by=c$.
      • Using bézout's identity.
      • We know that there must be some solutions $x_0,y_0$ where $a{x}_0+b{y}_0=d$
      • $a{x}_0+b{y}_0=d$
      • To avoid clashing of variables $c=kd$
      • $ka{x}_0+kb{y}_0=kd$
      • We know that $c=kd$ so: $ka{x}_0+kb{y}_0=c$
      • $k,a,b,x_0,y_0\in \mathbb{Z}$.
      • So we have $c=k(a{x}_0+b{y}_0)$
      • So if $d_2=a{x}_0+b{y}_0$ then we have $c=k{d}_2$.
  • b) if $a,b,c\in \mathbb{Z}$ and $d\ne 0$, show that $gcd(ad,bd)=|d|gcd(a,b)$
    • Defs:
      • $gcd(ad,bd)=d$
      • So $d\mid ad$ and $d\mid bd$, which is obvious
      • But $ad=qd$, $bd=rd$
      • For some $q,r\in \mathbb{Z}$

      ---

      • $|d|gcd(a,b)$
    • $⟹$
      • By Bézout's Identity we know that:
      • $(ad)x+(bd)y=gcd(ad,bd)=d$
      • $dax+dby=d$

Readings 05

Prop 1

• If $a\mid bc$ and $gcd(a,b)=1$ then $a\mid c$
• defs:
  • $a\mid bc$ means $bc=a{m}_1$
    • If $a\mid bc$ then $a\mid b$ or $a\mid c$ by the lectures.
    • so only one is true, $b=a{m}_2$ or $c=a{m}_3$
  • $gcd(a,b)=1$ means that $1\mid a$ and $1\mid b$ so then $a,b$ are co-prime.
    • $ax+by=1$
  • $a\mid c$ means $c=a{m}_1$
• $⟹$
  • We need to modulate this to show that $c=a{m}_1$
  • $ax+by=1$
  • $cax+cby=c$
  • $bc=a{m}_1$
  • $cax+a{m}_{1}y=c$
  • $a(cx+m_{1}y)=c$
  • $k_1=cx+m_{1}y$
  • So we get $c=a{k}_1$ which is the divisibility definition.

Theorem 4

• If $a,b,c\in \mathbb{Z}$ then $ax+by=c$ has a solution if and only if $gcd(a,b)\mid c$
  • Defs:
    • $ax+by=c$ is a linear diophantine and also bézout
      • $ax+by=c$ means $gcd(a,b)=c$
      • $c\mid a$ and $c\mid b$
      • $c=a{m}_2$ and $c=b{m}_3$
    • $gcd(a,b)\mid c$
      • $gcd(a,b)=g$
      • $g\mid c$ so $c=g{m}_1$
      • for some $m_i\in \mathbb{Z}$
• $⟹$
  • Let's modulate $ax+by=c$ into $c=g{m}_1$
  • $ax+by=c$
  • Solution would be $(x_0,y_0)$
  • $a{x}_0+b{y}_0=c$

Worksheet 05

• 1
  • a) Let $a\in \mathbb{N}$ and write $a$ in terms of its prime factorization $a=p_1^{a_1}{p}_2^{a_2}\dots p_n^{a_n}$. Show that $b\in \mathbb{N}$ divides $a⟺b$ has a prime factorization $b=p_1^{d_1}{p}_2^{d_2}\dots p_n^{d_n}$, where $0\le d_i\le a_i$ for $i=1,\dots ,n$
    • $a=p_1^{a_1}{p}_2^{a_2}\dots p_n^{a_n}$
    • $b=p_1^{d_1}{p}_2^{d_2}\dots p_n^{d_n}$
    • $b\mid a$ means:
      • $a=kb$
    • $⟹$
      • We need to modulate $a=kb$ into $b$'s prime factors.
      • So we know that these are the same primes, just a different exponent
      • $p_1^{a_1}{p}_2^{a_2}\dots p_n^{a_n}=k(p_1^{d_1}{p}_2^{d_2}\dots p_n^{d_n})$
      • Let the prime factorization of $k$ be $k=p_1^{k_1}{p}_2^{k_2}\dots p_n^{k_n}$ for $i=1,\dots ,n$
      • so we have
      • $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}\cdot p_1^{d_1}{p}_2^{d_2}\dots p_n^{d_n}$
      • $p_1^{a_1}{p}_2^{a_2}\dots p_n^{a_n}=p_1^{k_1+d_1}{p}_2^{k_2+d_2}\dots p_n^{k_n+d_n}$
      • When we equate these:
        • $a_i=k_i+d_i$
        • Which clearly shows that $a_i\ge d_i$

      ---

      • This works if the primes are the same, but the exponents are different. So here we basically show that if I'm able to have everything as a prime factorization, and I just add the exponents from the prime factorization of $k$ to $b$, then we get $a$.
    • $⟸$
      • Let's assume $b$ has a prime factorization. Can we get $a=kb$?
      • $b=p_1^{d_1}{p}_2^{d_2}\dots p_n^{d_n}$
      • $k=p_1^{a_1-d_1}{p}_2^{a_2-d_2}\dots p_n^{a_n-d_n}$
      • $a=p_1^{a_1}{p}_2^{a_2}\dots p_n^{a_n}$
      • $bk$
        • $p_1^{d_1}{p}_2^{d_2}\dots p_n^{d_n}\cdot p_1^{a_1-d_1}{p}_2^{a_2-d_2}\dots p_n^{a_n-d_n}$
        • Resulting in the prime factorization for $a=p_1^{a_1}{p}_2^{a_2}\dots p_n^{a_n}$
  • b) Suppose that $a,b\in \mathbb{N}$. Using a common prime factorization, 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}$
    • 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)}$
    • $⟹$
      • We know that if $gcd(a,b)=d$ then:
        • $d\mid a$ and $d\mid b$
        • so $a=qd,b=rd$ for some $q,r\in \mathbb{Z}$
      • $$gcd(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})=p_1^{min(a_1,b_1)}{p}_2^{min(a_1,b_1)}\dots p_n^{min(a_1,b_1)}$$
      • Let $d=p_1^{min(a_1,b_1)}{p}_2^{min(a_1,b_1)}\dots p_n^{min(a_1,b_1)}0$
      • So then it's obvious that $d\mid a$ and $d\mid b$, for all $min(a_n,b_n)$ we are the least of the two, so we will divide either the minimum of the two exponents or the maximum, as the max would be a multiple of any $p_n$.
  • c) Determine $gcd(9^4\cdot {10}^2,{12}^3)$
    • $\{\begin{array}{lll}656100& =1728(379)& +1188\\ 1728& =1188(1)& +540\\ 1188& =540(2)& +108\\ 540& =108(5)& +0\end{array}$
    • $gcd(9^4\cdot {10}^2,{12}^3)=108$
    • Other way
    • $9^4\cdot {10}^2$
      • $(3^2{)}^4\cdot (2\cdot 5{)}^2$
      • $2^2\cdot 3^8\cdot 5^2$
    • ${12}^3$
      • $2^2\cdot 3$
      • $(2^2\cdot 3{)}^3$
      • $2^6\cdot 3^3$
    • What's common between the two is:
      • $2^2\cdot 3^3$ is common
      • $2^2\cdot 3^3=108$
• 2. If $a,b\in \mathbb{Z}$, we say $c$ is a common multiple of $a$ and $b$ if $a\mid c$ and $b\mid c$. The $\text{lcm}$ of $a$ and $b$ is $\text{lcm}(a,b)$, which is also the smallest positive integer divisibly by both $a$ and $b$.
  • a)
    • Find the lcm of:
    • 1
      • $\text{lcm}(3,5)$
      • This is $\frac{3\cdot 5}{gcd(3,5)}$
      • They're co-prime, so this is just 15
  • b)
    • If $a,b\in \mathbb{N}$ then their $\text{lcm}$ exists.
    • Proof:
      • We know that the formula for $\text{lcm}$ is $\frac{1}{|gcd(a,b)|}\cdot ab$
      • Let the set $S=\{n\in \mathbb{N}:a\mid n\text{ and }a\mid b\}$
      • $gcd(a,b)=d$ and $d\in S$
      • so $d\mid a$ and $d\mid b$
      • $\frac{ab}{|d|}$
      • We know that $ab\in S$ because $a\mid ab$ and $b\mid ab$, we also know that $a,b\in \mathbb{N}$ so this holds.
      • Because $ab$ is in $S$, via the well-ordering principle, we know that $S$ has a least element, if $ab$ is simply an element which is a common multiple. The Well-Ordering Principle says that a non-empty set must have a least element. Which means least common multiple.
  • c) Supposer $a,b\in \mathbb{N}$. Using a common set of distinct primes, $p_1^{a_1}{p}_2^{a_2}\dots p_n^{a_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 the $a_i$ and $b_i$ may be zero.
    • Show that $\text{lcm}(a,b)=p_1^{min(a_1,b_1)}{p}_2^{min(a_1,b_1)}\dots p_n^{min(a_1,b_1)}$
    • Proof:
      • Let the $\text{lcm}(a,b)=d$
      • Let's show that $d$ has the same prime factorization as $a,b$
        • Suppose $d$ has a prime factorization:
          • $d=q_1^{d_1}{q}_2^{d_2}\dots q_n^{d_n}$
        • We know that $d$ is the $\text{lcm}(a,b)$ so, $a\mid d$ and $b\mid d$
        • Which means:
          • $d=a{m}_1$
          • $d=b{m}_2$
        • So $d$ is some multiple of $a,b$
        • Let $m_1,m_2$ have a prime factorization of $p_1^{o_1}{p}_2^{o_2}\dots p_n^{o_n}$
        • $q_1^{d_1}{q}_2^{d_2}\dots q_n^{d_n}=(p_1^{o_1}{p}_2^{o_2}\dots p_n^{o_n})(p_1^{a_1}{p}_2^{a_2}\dots p_n^{a_n})$
        • The above shows that $d$ is a multiple of $a$.

Readings 06

Worksheet 06