MAT102 Lecture 12

• 2
  • a
    • $6x\equiv 2\text{ mod }8$
    • $8\mid 2-6x$
    • $2-6x=8a$ for some $a\in \mathbb{Z}$.
    • $2-6x=8a$
      • $2-6x=8a$
      • Let's set some vars.
      • $x=3$
      • Let's sub in.
      • $2-6(3)=8a$
      • $2-18=8a$
      • $-16=8a$
      • $-\frac{16}{8}=a$
      • $-2=a$.
      • So we found a solution to our original statement.
    • Does $6x\equiv 3\text{ mod }8$ have a solution?
    • $8\mid 3-6x$
    • $8a=3-6x$
      • Doesn't seem so.
      • I don't think there is an integer solution for $a$.
  • b
    • Prove that the equation $ax\equiv c\text{ (mod }m)$ has a solution $x=x_0$ if and only if there exists a $y_0\in \mathbb{Z}$ such that $a{x}_0+m{y}_0=c$.
    • So if we have $ax\equiv c\text{ (mod }m)⟹m\mid c-ax$, this means $c-ax=mk$ for some $k\in \mathbb{Z}$.
    • Let's isolate $ax$:
      • $c-ax=mk$
      • $-ax=mk+c$
      • $ax=c-mk$.
      • $x=\frac{c-mk}{a}$
    • $⟹$
      • Let $x_0=\frac{c-mk}{a}$
      • $a\left(\frac{c-mk}{a}\right)+m{y}_0=c$
      • $\left(\frac{a(c-mk)}{a}\right)+m{y}_0=c$
      • $c-mk+m{y}_0=c$
      • $-mk+m{y}_0=0$
      • $-m(k-y_0)=0$
      • This shows us that $k-y_0$ is divisible by $m$.
      • $k-y_0=0$
      • $-y_0=-k$
      • $y_0=k$
      • This also shows us that there is a solution for $y_0$. At least in this direction.

      ---

      • Doesn't seem right, let's try again.
      • If we have $x=x_0$ as a solution for the congruence statement, then we have:
        • $a{x}_0\equiv c\text{ (mod }m)$
        • This means $m\mid (a{x}_0-c)$
        • So $a{x}_0-c=mk$ for some $k\in \mathbb{Z}$.
        • So isolating for $a{x}_0$
          • $a{x}_0=mk+c$
        • So we have $mk+c+m{y}_0=c$ if we sub into the diophantine equation.
        • $mk+c+m{y}_0=c$
        • $mk+m{y}_0=0$
        • $m(k+y_0)=0$
        • $k+y_0=0$
        • $y_0=-k$
        • So there is a solution for $y_0$.
    • $\Leftarrow$
      • Now we want to show if we have a solution $y_0$ for $ax+m{y}_0=c$.
      • This means that $gcd(a,m)=c$
      • So $c\mid a$ and $c\mid m$.

• Solutions
• 2
  • b
    • $⟹$
      • Suppose $a{x}_0\equiv c\text{ (mod }m)$
      • This means:
        • $m\mid (c-a{x}_0)$
        • So $\mathrm{\exists }{y}_0\in \mathbb{Z}$ such that $m{y}_0=c-a{x}_0⟹a{x}_0+m{y}_0=c$
    • $\Leftarrow$
      • Suppose $a{x}_0+m{y}_0=c$, reducing $\text{(mod }m)$
        • $m\text{ mod }m=0$
        • So we reduce this
        • Basically take $\text{mod }m$ of everything.
        • Congruence works with $\text{mod }m$ on both sides of the equation.
      • $a{x}_0\equiv c\text{ (mod }m)$
  • c
    • 1
      • We know $ax\equiv c\text{ (mod }m)$ has a solution, if and only if $ax+my=c$ has a solution.
      • From the readings, the diophantine equation has a solution if and only if $gcd(a,m)\mid c$.
    • 2
      • The solution to the linear diophantine eq is $x=x_0+\frac{m}{dk}$.
        • $d=gcd(a,m)$.
        • $k\in \mathbb{Z}$
      • $⟺x=x_0\text{ mod }\frac{m}{d}$
    • 3
      • $†$ = $S=\{x_0+\frac{m}{d}k,k\in \mathbb{Z}\}$
      • $††$ = $T=\{x_0+\frac{m}{d}k+\ell m\}k,\ell \in \mathbb{Z}$
      • Show $S=T$