MAT102 Tutorial W5

• 1
  • a
    • Show that if $gcd(a,b)\nmid c$
    • Let $d=gcd(a,b)$
    • $d\nmid c$
    • That $ax+by=c$ has no integer solutions
    • Let's proceed with contradiction, assume that $ax+by=c=d$ has an integer solution for $x,y\in \mathbb{Z}$.
    • This means that $d\mid a$ and $d\mid b$.
      • This also means that $a=dk$ and $b=dj$ for some $k,j\in \mathbb{Z}$
      • If you divide two numbers, then you divide any linear combination.
    • $(dk)x+(dj)y=c$
    • $dkx+djy=c$
    • $d(kx+jy)=c$
      • This shows us that $d\mid c$ because $d,k,j,y,x\in \mathbb{Z}$
      • Which means that there is an integer solution. This is a contradiction.

    ---

    • $d=gcd(a,b)$
    • $d\mid a$ and $d\mid b$
    • $d\mid ax$ and $d\mid by$
    • $d\mid ax+by$
    • $d\mid c$
    • Contradiction
  • b
    • Find $gcd(12,8)$

    ---

    • $gcd(12,8)=4$
    • $12x+8y=7$ does this have an integer solution?
    • $\{\begin{array}{ll}12& =8(1)+4\\ 8& =4(2)+0\end{array}$
    • No
    • $4\nmid 7$
• 2
  • a
    • $lcm(6,10)$ 'Lowest common multiple'
    • $a\mid 6$
    • $a\mid 10$
    • What is the lowest value of $a$ for each?
    • Prime factors for 6
      • $6=2\cdot 3$
      • $10=2\cdot 5$
      • $2^1\cdot 3^1\cdot 5^1$
      • $30$
    • $lcm(6,10)=30$

    ---

    • $gcd(6,10)=2$
    • $lcm(6,10)=\frac{|ab|}{gcd(a,b)}$
    • $lcm(6,10)=\frac{|6\cdot 10|}{2}$
    • $lcm(6,10)=\frac{60}{2}$
    • $lcm(6,10)=30$
  • b
    • if $a,b\in \mathbb{N}$
    • show that $lcm(a,b)=\frac{ab}{gcd(a,b)}$
    • Proof
      • To show $\frac{ab}{gcd(a,b)}=lcm(a,b)$
      • Need to show first that $a\mid RHS$ and $b\mid RHS$.
      • Let $d=gcd(a,b)$
      • Note that from our $gcd$ we have $a=dk$ and $b=dl$ for some $k,l\in \mathbb{N}$.
      • Let $m=\frac{ab}{d}$
        • Notice that $m=\frac{(dk)(dl)}{d}$
        • $m=\frac{(dk)(b)}{d}$
        • $m=\frac{dkb}{d}$
        • $m=kb$ this $⟹b\mid m$
        • $m=\frac{adl}{d}$
        • $m=al$ this $⟹a\mid m$
      • Now we need to show that this is the smallest multiple.
      • let's have $c$ be another multiple of $a,b$ such that $c=ax=by$ where $x,y\in \mathbb{Z}$
      • If $\frac{c}{m}\in \mathbb{Z}$ then this automatically means that $c$ is greater than $m$ and is a multiple.
        • $⟹m\mid c$
      • See that $\frac{c}{m}=\frac{c\cdot d}{ab}$
      • $=\frac{c(ad+bt)}{ab}$ by bézout's identity.
      • $\frac{cas}{ab}+\frac{cbt}{ab}$
        • $s,t\in \mathbb{Z}$
      • Sub in $ax$ or $by$
      • $\frac{cs}{b}+\frac{ct}{a}$
      • $\frac{(by)s}{b}+\frac{(ax)t}{a}$
      • $ys+xt$, this is $\in \mathbb{Z}$.
      • We now know that $m\mid c$ which $⟹$ that $m\le c$ which means $m$ is the least common multiple.
• 3
  • Show that there is no integers $x$ such that $0<x<1$.
  • let's define a set $A=(0,1)$
  • $B=\{0,1\}$
  • $B⊈A$
  • Let $x\in A$
  • Let's proceed with contradiction:
    • Let's assume there is an integer $x$ that is in $A$.
    • $A⊈\mathbb{N}$
    • So there is no way that we can use the well ordering principle to find the minimal element.
    • $x\in A$

  ---

  • Proof:
    • Suppose for the sake of contradiction there are integers in $(0,1)$.
      • This is a non-empty set, so there is an integer in there, so there is some ordering going on.
    • By the well-ordering principle, we know that $n\in (0,1)$ is the smallest number.
    • $0<n<1$
    • This means
      • $0<n^2<n$ Multiply $n$ on both sides.
      • $0<n^2<n<1$
      • $n$ should have been the smallest number, but $n^2$ is smaller than $n$.
      • We violate the well-ordering principle, which is a contradiction.
      • You can also set up that $j=\frac{n}{2}$ which is less than $n$ which also violates the well-ordering principle.