MAT102 Lecture 11

• $9+5\text{ mod }12$
  • This is the same as finding $9am+5hours=2pm$
  • $9+5\equiv 2\text{ mod }12$
• $49\equiv -1\text{ mod }10$
• Equivalence Classes
  • If $\sim$ is an equivalence relation on S,
  • $[a]=\{x\in S:a\sim x\}$
  • For example mod $10$.
    • $[-1]=\{\dots ,-11,1,9,19,29,39,49,\dots \}$
    • $[-1]$ is a representative of the equivalence class.
  • $[-8]+[3]=[5]$
  • $[-8]+[3]=[15]$
• $ax=c\text{ mod }b$
• $⟺b\mid (ax-c)$
• $⟺\mathrm{\exists }y,by=ax-c$
• $⟺ax-by=c$
• $⟺ax+b(-y)=c$
• $⟺ax+b\hat{y}=c$
• $\hat{y}=-y$

• Transitive Playbook
  • Take the first equation, manipulate the second equation to fit into the first, then sub and simplify to reach our third equation.
• 1
  • Reflexive
    • Let $x\in \mathbb{R}$, we want to show that $x\sim x$.
    • $x^2+x=x^2+x$, clearly true.
  • Symmetry
    • If $x=y$ then $y=x$
    • Assume $x\sim y$:
      • Let $x,y\in \mathbb{R}$ such that $x\sim y$.
      • That means $x^2+y=y^2+x$
    • Now show other direction.
      • To show $y\sim x$, we need that $y^2+x=x^2+y$
      • This is true by assumption.
      • The thing is that the order doesn't matter, like how $a\equiv b\text{ mod }10$ is $10\mid (b-a)$ or $10\mid (a-b)$. Because $10$ would divide either (example) $50$ or $-50$.
  • Transitivity
    • Assumption: Suppose that $x\sim y$ and $y\sim z$. Namely $x^2+y=y^2+x$, $y^2+z=z^2+y$.
    • Can we use $y$ to bridge the gap between $x$ and $z$.
    • Now want to show that $x\sim z$ or that $x^2+z=z^2+x$.
    • Don't do $0=0$ cause that's wrong.
    • Doing some algebra, we get:
      • $x^2+z$
        • How can we add $y$ into this equation?
      • $x^2+y-y+z$
      • $(x^2+y)-y+z$
      • $y^2+x-y+z$
        • now let's use the other equation.
      • $(y^2+z)+x-y$
      • $z^2+y+x-y$
      • $z^2+x$
      • We've shown that $x^2+z=z^2+x$ through adding and subbing in our equations including $y$.
    • Thus this is transitive.
• 2
• 3
  • $S_1=\{0,1,2,3,\dots \}$ and $S_2=\{0,-1,-2,\dots \}$
  • Can there be an equivalence class for this relation $\sim$ on $\mathbb{Z}$?
  • You can't just be a $\subseteq \mathbb{Z}$ to be an equivalence relation. That's not the only pre-requisite.
  • From the reading:
    • If $\sim$ is an equivalence relation, then $[a]\cap [b]=\mathrm{\varnothing }⟺a\nsim b$.
    • For an equivalence relation, the sets must be equal or disjoint.

  ---

  • If $a\in S_1$ then $a\sim 0$. Because $0$ is in $S_1$.
  • If $b\in S_2$ then $b\sim 0$. By transitivity then $a\sim b$.
  • This means that everything in $S_1$ is in $S_2$ and vice versa.
• 4
  • Let $n\in \mathbb{N}$ with $n\ge 2$
  • Suppose $a,b\in \mathbb{Z}$ satisfy $a\equiv b(\text{mod }n)$.
  • $3a\equiv 3b(\text{mod }n)$
  • $n|3b-3a$
  • $n|0$
  • $0=an$ for some $a\in \mathbb{Z}$

  ---

  • $\{\begin{array}{l}n=3\\ a=3\\ b=0\end{array}$
  • $a\equiv b\text{ mod }n$
  • $2^a\equiv 2^b\text{ mod }n$
  • $2^3{\equiv }_8\text{ mod }3\equiv 2\text{ mod }3$
  • $2^0\equiv 1\text{ mod }3\equiv 1\text{ mod }3$
• 5
  • The last digit of $7^{20}$ is.
  • $d=7^{20}\text{ mod }10$
  • $7^{20}=(7^2{)}^{10}=(49{)}^{10}\text{ mod }10$

  ---

  • We want the $7^{20}\text{ mod }10$.
  • $7^{20}=(7^2{)}^{10}=(49{)}^{10}\equiv (-1{)}^{10}\text{ mod }10$
    • ${49}^{10}\text{ mod }10$, keep on subtracting 10 until we get $-1$. So they're congruent. This means that we can put $-1$ in the equation.
  • $\equiv 1\text{ mod }10$

Worksheet

• MAT102 - Worksheet 6.pdf
• 1
  • A relation on $P$ is $S_R\subseteq P\times P$. is $x⊢y$ if $y-x\in P$.
  • a
    • Show that $⊢$ is transitive.
    • It is not reflexive or symmetric.
    • We need to show that $x-y=y-z$.
    • Assume that $x⊢y$ and $y⊢z$.
    • $y-x\in P$ and $z-y\in P$
    • Want to prove $z-x\in P$
    • $z-x$
    • $z-x+y-y$
    • $(z-y)-x+y$
    • $(z-y)+(y-x)$
    • $(z-y)\in P$ and $(y-x)\in P$
    • so we show that this is transitive

    ---

    • Suppose $x⊢y$ and $y⊢z$
    • This means that $y-x\in P$ and $z-y\in P$.
    • $z-x$
    • $z-y+y-x$
    • $(z-y)+(y-x)$ The whole thing is in $P$ because of $P2$
  • b
    • Show that if $c\in P$ and $x⊢y$ then $cx+cy$.
    • Suppose $x⊢y$ and $c\in P$.
    • By assumption we know $y-x\in P$
    • Therefore
      • Show that $c(y-x)\in P$
      • So show $c\in P$ and $y-x\in P$
    • If $c\notin P$ then $-c\in P$
    • $cx-cy=-c(y-x)\in P$
    • Both are $\in P$
  • c
    • Show that if $x⊢y$ and $u⊢v$, then $x+u⊢y+v$
    • If $x⊢y$ this means $y-x\in P$
    • If $u⊢v$ this means $v-u\in P$
    • Then $x+u⊢y+v$
    • $(y+v)-(x+u)$
    • We know that any two numbers in $P$, their sums are also in $P$.
    • So by $P2$, if $y\in P$ and $v\in P$ then $y+v\in P$.
    • $y+v-x-u$
    • $y-x+v-u$
    • $(y-x)+(v-u)$
    • This also formally shows this. Since we already knwe $y-x\in P$ and $v-u\in P$.
  • d
    • If $x,y\in P$ and $x⊢y$, show that $x^2⊢y^2$.
    • If $x,y\in P$ this means that $x+y\in P$ as well as $xy\in P$
    • $x⊢y$ is $y-x\in P$
    • $x^2⊢y^2$ is $y^2-x^2\in P$
    • As we know that if $x,y\in P$ that $xy\in P$ as well.
    • Then this means $xx\in P$, so $x^2\in P$.
    • By the above $y^2\in P$.
    • This means $y^2-x^2\in P$ because the multiplication of any element in this set $P$ by itself, or another element of the same set will still be in the set $P$.
  • e
    • If $x,y\in P$ and $x⊢y$, show that $\frac{1}{y}⊢\frac{1}{x}$.
    • Suppose $x⊢y$ so $y-x\in P$
    • $\frac{y-x}{xy}\in P$.
      • We see that the top is in P and denom in P because of $P2$
  • f
    • This is $<$. The relation is $<$.
• 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$
      • $a=1$
      • $x=3$
    • $2-6x-8a=0$
    • $-6x-8a=-2$
    • $6x+8a=2$
    • $6x=2-8a$
    • $x=\frac{2-8a}{6}$
    • Does $6x\equiv 3\text{ mod }8$ have a solution?
    • $8\mid 3-6x$
    • $8a=3-6x$
      • Doesn't seem so.
  • b
    • Prove that $ax\equiv c\text{ mod }m$ has a solution $x=x_0$ if and only if $\mathrm{\exists }{y}_0\in \mathbb{Z}$ such that $a{x}_0+my=c$