• ↑
  • MAT102 Final Exam Prep

MAT102 Worksheet 4 Review

Q1

• Show that the equation $x^3+2y^3=4z^3$ has no positive integer solutions.
• Let's assume we have a solution - $(x_0,y_0,z_0)$ -

A

• Argue that $x_0$ must be even.
• Let's consider a case where $x_0$ is even.
• Thus $x_0=2x$
• So we have $(2x{)}^3+2y^3=4z^3$
• $(2x)(2x)(2x)+2y^3=4z^3$
• $(4x^2)(2x)+2y^3=4z^3$
• $8x^3+2y^3=4z^3$
• Notice we can pull out a $2$
• $4x^3+y^3=2z^3$
• Since we were able to pull out a $2$, this must mean that $x_0$ is even.

B

• Now notice how we were able to divide by $2$. Meaning that everything was able to be expressed as $2\cdot \text{something}$. Exactly the definition of evenness.
• Let's assume that $y_0,z_0$ are even, so $\begin{array}{c}{y}_0=2y\\ z_0=2z\end{array}$
• $(2x{)}^3+2(2y{)}^3=4(2z{)}^3$
• $8x^3+16y^3=32z^3$
• Divide by $2$ for $y$
• $4x^3+8y^3=16z^3$
• Divide by $2$ for $z$
• $2x^3+4y^3=8z^3$
• Then divide by $2$ again for $x$
• $x^3+2y^3=4z^3$
• Notice how we were able to divide our assumed solution's even definition multiple times, just enough to take out $2$ from each solution.
• This must mean that $x,y,z$ are even.

C

• If $(x_0,y_0,z_0)$ is a solution of positive integers.
• Then there is a solution $(x_1,y_1,z_1)$ such that $x_1<x_0,y_1<y_0$ and $z_1<z_0$
• Watch what happens, since everything is even, we can say $x_0=2x$, and that $x_1=2x_0$
• Do the same for everything else such that $y_1=2y_0,z_1=2z_0$
• $(2x_0{)}^3+2(2y_0{)}^3=4(2z_0{)}^3$
• $(8x_0{)}^3+(16y_0{)}^3=(32z_0{)}^3$
• $x_0^3+2y_0^3=4z_0^3$
• As required.

D

• This is a contradiction, because we just found another solution that's smaller than the original assumed solution.
• So we can keep on creating solutions $\begin{array}{c}\underbrace{(x_i,y_i,z_i)}\\ x_i=1,2,\dots ,i\\ y_i=1,2,\dots ,i\\ z_i=1,2,\dots ,i\end{array}$
• So if we can keep making smaller solutions, then there are no solutions. This models the 'no smallest real number' proof.

Q2

A

• Show that the equation $ax+by=c$ has a solution $⟺gcd(a,b)\mid c$.
• $⟹$
  • Assume that $ax+by=c$ has a solution.
  • Let's show that the $gcd(a,b)\mid c$.
  • The definition of gcd, is:
    • $gcd(a,b)=d$
    • So $d\mid a$ and $d\mid b$
  • $a=dk,b=dj$ for some $k,j\in \mathbb{Z}$
  • If $d\mid c$ then $c=dh$ for some $h\in \mathbb{Z}$
  • $dkx+djy=c$
  • $d(kx+jy)=c$
    • We established $k,j\in \mathbb{Z}$, but $x,y$ are also $\in \mathbb{Z}$.
  • So let $h_0=kx+jy$
  • Notice we have $d{h}_0=c$, so we have shown as required that this works.
• $⟸$
  • So we assume that $gcd(a,b)\mid c$
  • Let $gcd(a,b)=d$
    • $d\mid a$
      • $a=dk$ for some $k\in \mathbb{Z}$
    • $d\mid b$
      • $b=dj$ for some $j\in \mathbb{Z}$
  • So this means that $c=dh$ for some $h\in \mathbb{Z}$
  • We want to show that $ax+by=c$ has a solution
  • By bézout's identity, we know that if $gcd(a,b)=d$ then $ax+by=d$
  • So if the result is multiplied by $c$, then it still holds. There are still solutions that reach $c$ with $ax+by$.
  • Notice that $c=dh$
  • So there is a scalar of $h$ on $d$.
  • $ax(h)+by(h)=dh$
  • $(dk)x(h)+(dj)y(h)=c$
  • $dkxh+djyh=dh$
  • $\frac{dkxh+djyh}{d}=\frac{dh}{d}$
  • $kxh+jyh=h$
  • $kx+jy=1$
  • This shows that we have a solution. If $kx+jy=1$, then $1\cdot h$ gets us to a position where it would reach $h$. Multiplying further by $d$ will get us to $dh$, which we defined as $c=dh$, so it gets us to $c$.
  • $◻$

B

• If $a,b,c\in \mathbb{Z}$ and $d\ne 0$, show that $gcd(ad,bd)=\left|d\right|gcd(a,b)$
• Let $gcd(ad,bd)=d_1$
• So then $ad=d_{1}k,bd=d_{1}j$ for some $k,j\in \mathbb{Z}$
• Let $gcd(a,b)=d_2$
• So $a=d_{2}h,b=d_2\ell$ for some $h,l\in \mathbb{Z}$
• We want to show that $d_1=\left|d\right|d_2$
• $adx+bdy=d_1$
• $ax+by=d_2$
• Notice the only scalar here is $d$.
• So $d_1\cdot \left|d\right|=d_2$ via $ax+by=d_2⟹\left|d\right|ax+\left|d\right|by=\left|d\right|\cdot d_1$
• So this shows that
• $◻$