MAT102 Term Test 2 Prep

Readings 6

06FunctionsII.pdf

• Example 3:
  • Determine whether each function below is invertible
  • 1
    • $f:{\mathbb{R}}^2\to {\mathbb{R}}^2,f(x,y)=(2x,x-y)$
    • $f^{-1}(f(x))=i{d}_{\circ }(x)=x$
    • $f^{-1}(f(x))=i{d}_{\circ }(y)=y$
    • $z=2x$
    • $\frac{z}{2}=x$
    • $w=x-y$
    • $w=\frac{z}{2}-y$
    • $w-\frac{z}{2}=y$
    • $f^{-1}(z,w)=(\frac{z}{2},-w+\frac{z}{2})$
    • $f^{-1}(f(x))=(\frac{2x}{2},-(x-y)+\frac{2x}{2})$
    • $f^{-1}(f(x))=(\frac{2x}{2},-x+y+\frac{2x}{2})$
    • $f^{-1}(f(x))=(x,y)$
  • 2
    • $g:{\mathbb{Z}}^{+}\to {\mathbb{Z}}^{+}$
    • $g(n)={10}^{n+1}+1$
    • $g^{-1}(g(n))=i{d}_{\circ }(n)=n$
    • Let the transformation be $x$
    • $x={10}^{n+1}+1$
    • $x-1={10}^{n+1}$
    • ${\log }_{10}(x-1)=n+1$
    • ${\log }_{10}(x-1)-1=n$
    • $x-1>0$
    • $x>1$
    • doesn't work because of the restriction, won't work for first case
• Exercise 4
  • Come up with sets $A$ and $B$ and a function $f:A\to B$ such that:
    • $g:B\to A$ where $f\circ g=i{d}_{\circ }^B$ but $g\circ f\ne i{d}_{\circ }^A$
      • $g\circ f\ne i{d}_{\circ }^A$
      • $g\circ f:A\to A$
      • $f:A\to B,x\mapsto x^2$
      • $g\circ f:A\to A$ and then we have a case where we're wondering which $x$ created that $y$.
      • $f\circ g:B\to B$
      • Surjective, not injective
    • $g:B\to A$ where $g\circ f=i{d}_{\circ }^A$ but $f\circ g\ne i{d}_{\circ }^B$
      • Injective, not surjective
• Exercise 6
  • If $f:S\to T$ is a function, $f$ is invertible $⟺f$ is bijective
  • $⟸$
    • Suppose that $f$ is bijective, define $g:T\to S$ as follows:
      • Fix $t\in T$ and consider $f^{-1}(\{t\})$, this is non-empty as $f$ is surjective, and it's $1$ element since $f$ is injective.
      • Call this element $s_t$
    • Define $g(t)=s_t$
    • Claim $g$ is the inverse of $f$
    • $f(g(t))=f(s_t)=t$
    • $s_t\in f^{-1}(\{t\})$
    • See that $g(f(s))=s_{f(s)}$, then $s_{f(s)}=s$
  • $⟹$
    • $f:S\to T$ is invertible
    • This means by exercise 4 that $g:T\to S$ has $g\circ f=i{d}_{\circ }^S$ and $g:T\to S$ has a $f\circ g=i{d}_{\circ }^T$.
    • To achieve the first case, we need to be surjective, the second, we need to be injective.
    • Because we are both, we are bijective.
• Exercise 9
  • Show that if $S\subseteq T$ then $\left|S\right|\le \left|T\right|$
  • Show that there's an injection $f:S\hookrightarrow T$ where $f(s)=s$
  • Injective
    • $f(a)=f(b)⟹a=b$
    • $f(a)=a$
    • $f(b)=b$
    • $a=b$
    • So it's injective
  • Because it's injective, this means that $\left|S\right|\le \left|T\right|$
• Example 12
  • $2\mathbb{N}=\{0,2,4,6\}$
  • Show that $\left|2\mathbb{N}\right|=\left|\mathbb{N}\right|$
  • We need to construct an injection both ways, or bijection directly.
  • Bijection
    • $f:\mathbb{N}\to 2\mathbb{N}$
    • $f(n)=2n$
    • Injection
      • $f(a)=f(b)$
      • $2a=2b$
      • $a=b$
    • Surjection
      • Fix an arbitrary $n_0\in \mathbb{N}$
      • $f(a)=n_0$
      • $2n=n_0$
      • See that any element from $2\mathbb{N}$ can be created from an element in $\mathbb{N}$.
  • This is explicitly bijective so it's the same Cardinality.
• Exercise 13
  • Show that $|(0,1)|=\left|\mathbb{R}\right|$
  • Injection from $f:(0,1)\hookrightarrow \mathbb{R}$
  • Defined as $f(r)=r$
  • Injective:
    • $f(a)=f(b)$
    • $a=b$
  • Injection from $g:\mathbb{R}\hookrightarrow (0,1)$
  • Defined as $g(r)=\frac{1}{\pi }\arctan (r)$
• Exercise 19
  • Show that $|\mathbb{N}\times \mathbb{N}|=\left|\mathbb{N}\right|$
  • Injection $f:\mathbb{N}\times \mathbb{N}\to \mathbb{N}$
  • Let $f(a,b)=2^a{3}^b$
  • Injective
    • $f(a,b)=f(c,d)$
    • $2^a{3}^b=2^c{3}^d$
    • By FTA we have unique prime factorizations.
  • Injection $g:\mathbb{N}\to \mathbb{N}\times \mathbb{N}$
  • Let $g(n)=(n,n)$
    • $g(a)=g(b)$
    • $(a,a)=(b,b)$
    • $a=b$
  • By CSB, there is a bijection so they have the same Cardinality
• 1
  • Determine whether it's invertible
  • a:
    • $r:\mathbb{R}\to \{0,1\},r(q)=\{\begin{array}{ll}1& q\in \mathbb{Q}\\ 0& q\notin \mathbb{Q}\end{array}$
    • $r^{-1}(r(x))=i{d}_{\circ }^{\{0,1\}}=x$
    • $r(r^{-1}(x))=i{d}_{\circ }^{\mathbb{R}}=y$
    • It's not invertible because it's not bijective
    • See that many rationals map to $1$
    • $\frac{1}{2}\mapsto 1$
    • $\frac{1}{3}\mapsto 1$
  • b:
    • $c:\mathbb{R}\to \mathbb{R}$
    • $c(x)=x^3$
    • $z=x^3$
    • $x=\sqrt[3]{z}$
    • Let's see if the transformation $z$ will give us the identity
    • $c(c^{-1}(x))=x$
    • $c(\sqrt[3]{x})=x$
    • $(\sqrt[3]{x}{)}^3=x$
    • $x=x$
    • $c^{-1}(c(x))=x$
    • $c^{-1}(x^3)=x$
    • $\sqrt[3]{x^3}=x$
    • $x=x$
• 2
  • A function $f:A\to B$ is left-invertible if there is $g:B\to A$ such that $g\circ f=i{d}_{\circ }^A$
  • Show that $f$ is left-invertible $⟺$ is it injective
    • $⟹$
      • $f$ is left-invertible so there is $g:B\to A$ such that $g\circ f=i{d}_{\circ }^A$
      • Want to show that $f(a)=f(b)⟹a=b$
      • $g:(f:A\to B)\to A$
      • $i{d}_{\circ }^A:A\to A$
      • The nature of this necessity means that there shouldn't be a loss of information from $f\to g$
      • $g(f(a))=g(f(b))$
      • $(g\circ f)(a)=(g\circ f)(b)$
      • $i{d}_{\circ }^A(a)=i{d}_{\circ }^B(b)$
      • The identity function will always produce the input
      • $a=b$
    • $⟸$
      • We know that $f$ is injective
      • Show it's left-invertible
      • $f:A\to B$
      • We want to create some $g:B\to A$ where it creates $i{d}_{\circ }^A$
      • So then $f(a)=f(b)⟹a=b$
      • $g\circ f=i{d}_{\circ }^A$
      • $i{d}_{\circ }^A:A\to A$
      • Since $f$ is injective, the outputs are unique, there are no two outputs for one input.

Readings 7

07NumberTheoryI.pdf

• Exercise 2
  • For what values of $n$ does $n\mid 0$
  • See that $nk=0$ for some $k\in \mathbb{Z}$
  • However this is true for all $k$.
• Exercise 4
  • if $a\mid b$ and $a\mid b+c$ then $a\mid c$
    • $ak=b$
    • $a\ell =b+c$
    • $aj=c$
    • for $k,\ell ,j\in \mathbb{Z}$
    • We know $ak=b$ and $a\ell =b+c$
    • Want to show that $aj=c$
    • $a\ell =ak+c$
    • $a\ell -ak=c$
    • $a(\ell -k)=c$
    • let $j=\ell -k$
    • Proven
  • if $a\mid b$ and $b\mid a$ then $a=\pm b$
    • $ak=b$
    • $b\ell =a$
    • for some $k,\ell \in \mathbb{Z}$
    • $a=ak\ell$
    • $j=k\ell$
    • $j=1$
    • Cases:
      • $k=1,\ell =1$
      • $k=-1,\ell =-1$
    • $a=ak\ell$
    • $a=b\ell$
    • then see that our only two options are $a=b$ or $a=-b$
  • if $b$ is non-zero and $a\mid b$ then $\left|a\right|\le \left|b\right|$
    • Let $a\mid b$ as $\left|ak\right|=\left|b\right|$ for some $k\in \mathbb{Z}$
    • We can then split them as $\left|a\right|\left|k\right|=\left|b\right|$
    • $\left|k\right|\ge 1$
    • This implies that $\left|a\right|\le \left|a\right|\left|k\right|=\left|b\right|$
    • $\left|a\right|\le \left|b\right|$
• Example 6
  • Show that for any $n\in \mathbb{Z}$ that $3\mid (n^3-n)$
  • $3k=n^3-n$ for some $k\in \mathbb{Z}$
  • $3k=n(n^2-1)$
  • $3k=n(n-1)(n+1)$
  • $n^3\equiv n(\mathrm{mod}3)$
  • FLT says that $a^p\equiv a(\mathrm{mod}p)$
  • So this is true
  • Directly:
  • Case 1: $n=3k$
    • $n$ is a multiple of $3$
    • The product of three consecutive numbers is divisible by $3$
  • Case 2: $n=3k+1$
    • $n-1⟹3k+1-1=3k$ which is another multiple of $3$
  • Case 3: $n=3k+2$
    • $n+1⟹3k+2+1=3k+3$
    • Another multiple of $3$
• Corollary 15
  • $a,b\in \mathbb{Z}$
  • $c\mid a$
  • $c\mid b$
  • then $c\mid gcd(a,b)$
  • $ax+by=gcd(a,b)$
  • $ck=gcd(a,b)$
  • $cax+cby=gcd(a,b)$
  • $c(ax+by)=gcd(a,b)$
  • let $k=ax+by$
  • $ck=gcd(a,b)$
• Corollary 16
  • If $a,b\in \mathbb{Z}$ the integer $d>0$ is a common divisor of both $a$ and $b$
  • $d\mid a$ and $d\mid b$
  • There exists $m,b\in \mathbb{Z}$ such that $am+bn=d$ then $d=gcd(a,b)$
  • $dk=a$ and $dj=b$
  • $dkm+djn=d$
  • $km+jn=1$
• Exercise
  • 1
    • Suppose that $a,b,c,d\in \mathbb{Z}$
    • Prove that if $ac\mid bc$ and $c\ne 0$ then $a\mid b$
      • $ack=bc$ for some $k\in \mathbb{Z}$
      • Want to show that $aj=b$ for some $j\in \mathbb{Z}$
      • $ak=b$
      • Done
    • Prove that if $a\mid b,c\mid d$ then $ac\mid bd$
      • $ak=b$ and $cj=d$
      • Want to show that $ac\ell =bd$
      • If we multiply them together: $(ak)(cj)=(b)(d)$
      • $ackj=bd$
      • let $kj=\ell$
      • $ac\ell =bd$
  • 2
    • Suppose that $n$ is odd
    • Show that $4\mid (n^2-1)$
    • $n=2k+1$
    • $4\ell =n^2-1=(n-1)(n+1)$
    • $4\ell =(n+1)(n-1)$
    • $4\ell =(2k+2)(2k)$
    • $4\ell =4k(k+1)$
    • So clearly $4\mid (n^2-1)$ as we have a multiple of $4$.
  • 4
    • Let $n\in {\mathbb{Z}}^{+}$ with $n\ge 2$
    • Show that for any $a\in \mathbb{Z}$ satisfying $gcd(a,n)=1$ there is a $b\in \mathbb{Z}$ such that $n\mid (ab-1)$
    • We know that $gcd(a,n)=1$
    • $ax+ny=1$
    • Want to show that $n\mid (ab-1)$
    • $nk=ab-1$ for some $k\in \mathbb{Z}$
    • Let's modify $ax+ny=1$
    • $ny=1-ax$
    • Clearly this shows that $n\mid 1-ax$ which means $n\mid ab-1$
    • All we are doing is changing the variable and sign
    • $ax\equiv 1(\mathrm{mod}n)$
    • So $a$ is the multiplicative inverse
    • $b=x$
    • So then $n\mid ab-1$
  • 5
    • If $a,b\in {\mathbb{Z}}^{\ast }$, show that $gcd(3a+2b,a+b)=gcd(a,b)$
    • The euclidean algorithm requires that $gcd(a,a+b)=gcd(a,b)$, meaning you can keep on adding or subtracting $b$ to $a$.
    • Euclidean Algorithm
      • $gcd(3a+2b,a+b)$
        • $3a+2b-(a+b)=2a+b$
        • $2a+b-(a+b)=a$
      • So $gcd(a,a+b)$
        • $a+b-a=b$
      • So $gcd(a,b)$
    • Lemma:
      • $gcd(a,a+b)=gcd(a,b)$
      • Let $gcd(a,a+b)=d_0$ and $gcd(a,b)=d_1$
      • $a{x}_0+(a+b)y_0=d_0$
        • $a{x}_0+a{y}_0+b{y}_0=d_0$
        • $a(x_0+y_0)+b{y}_0=d_0$
      • $a{x}_1+b{y}_1=d_1$

Readings 8

08NumberTheoryII.pdf

• Prop 1
  • If $a\mid bc$ and $gcd(a,b)=1$ then $a\mid c$
  • $ak=bc$ for some $k\in \mathbb{Z}$
  • $ax+by=1$
  • $cax+cby=c$
  • $cax+aky=c$
  • $a(cx+ky)=c$
  • So $a\mid c$
• Theorem 4
  • If $a,b,c\in \mathbb{Z}$ then $ax+by=c$ has a solution $⟺gcd(a,b)\mid c$
  • $⟹$
    • $ax+by=c$ has a solution
    • $a{x}_0+b{y}_0=c$
    • $d\mid a$ and $d\mid b$
    • $d\ell =a$
    • $dj=b$
    • $d\ell x_0+dj{y}_0=c$
    • $d(\ell x_0+j{y}_0)=c$
    • $i=\ell x_0+j{y}_0$
    • $di=c$
    • $\frac{d}{c}=i$
  • $⟸$
    • $gcd(a,b)\mid c$
    • $d\mid c$
    • Show that $ax+by=c$ has a solution
    • $dk=c$ for some $k\in \mathbb{Z}$
    • $ax+by=d$
    • $akx+bky=dk$
    • $a{x}_0+b{y}_0=c$
• Example 6:
  • Find a solution to $504x+1155y=42$
  • $\begin{array}{lll}1155& =504(2)& +147\\ 504& =147(3)& +63\\ 147& =63(2)& +21\\ 63& =21(3)& +0\end{array}$
  • $(2)(147+63(-2))=21(2)$
  • $(2)(147+(504+147(-3))(-2))=21(2)$
  • $(2)(504(-2)+147(7))=21(2)$
  • $(2)(504(-2)+(1155+504(-2))(7))=21(2)$
  • $(2)(1155(7)+504(-16))=21(2)$
  • $1155(14)+504(-32)=42$
  • $y=14$
  • $x=-32$
  • $x=x_0+n\frac{b}{d}$
    • $x=-32+55n$
  • $y=y_0-n\frac{a}{d}$
    • $y=14-24n$
• Theorem 13
  • A number $p\in {\mathbb{Z}}^{+}$ is prime $⟺$ for any $a,b\in \mathbb{Z}$, if $p\mid ab$ then $p\mid a$ or $p\mid b$
  • $\mathrm{\exists }p\in {\mathbb{Z}}^{+}\text{ is prime}:\mathrm{\forall }a,b\in \mathbb{Z},p\mid ab⟹p\mid a\vee p\mid b$
• Exercise 15
  • Show that primality is necessary for Theorem 13
  • if $p$ is not prime, show a counter example
  • $p\mid ab$ but $p\nmid a$ or $b$
  • $a=2$
  • $b=2$
  • $p=4$
  • $p\mid ab$
  • $4\mid 2\cdot 2$
  • $4\nmid 2$
  • $p=8$
  • $b=4$
  • $a=2$
  • $8\mid 8$ but $8\nmid 4\vee 2$
• Exercise 16
  • $n\in \mathbb{Z}$
  • $p$ is prime
  • $p\mid n⟺p\mid n^2$
  • $⟹$
    • $p\mid n$
    • $n\mid n^2$
    • By transitivity $p\mid n^2$
  • $⟸$
    • $p\mid n^2$
    • $p\mid n$
    • $pk=n^2$
    • $p\ell =n$
    • $pk=nn$
    • By theorem 13
    • if $p$ is prime, $p\mid ab$ then $p\mid a$ or $p\mid b$
    • $p$ is prime, $p\mid nn$
    • so $p\mid n$
• Theorem 20
• Exercises:
  • 2
    • How many $0$'s occur at the end of $100!$.
    • $n!=n(n-1)(n-2)\dots (3)(2)(1)$
    • The product of $n$ consecutive numbers is divisible by $n$
    • Multiples of $10$
  • 3
    • Let $a\in \mathbb{N}$ write $a$ in terms of its prime factorization
    • $a=p_1^{a_1}{p}_2^{a_2}\dots p_n^{a_n}$
    • $b\in \mathbb{N}$
    • $b\mid a⟺b=p_1^{b_1}{p}_2^{b_2}\dots p_n^{b_n}$ where $0\le b_i\le a_i$
    • $⟹$
      • $b\mid a$
      • $bk=a$ for some $k\in \mathbb{Z}$
      • $bk=p_1^{a_1}{p}_2^{a_2}\dots p_n^{a_n}$
      • Suppose that $b$ did not have the same prime factorization
      • $b=q_1^{b_1}{q}_2^{b_2}\dots q_n^{b_n}$
      • $q_1^{b_1}{q}_2^{b_2}\dots q_n^{b_n}k=p_1^{a_1}{p}_2^{a_2}\dots p_n^{a_n}$
      • Contradiction because this implies that the primes are not unique.
    • $⟸$
      • $b=p_1^{b_1}{p}_2^{b_2}\dots p_n^{b_n}$
      • Since it has the same primes as $a$
      • and $0\le b_i\le a_i$
      • then we have that $b_i+k_i=a_i$
      • Let $k=p_1^{k_1}{p}_2^{k_2}\dots p_n^{k_n}$
      • $p_1^{b_1}{p}_2^{b_2}\dots p_n^{b_n}{p}_1^{k_1}{p}_2^{k_2}\dots p_n^{k_n}=p_1^{a_1}{p}_2^{a_2}\dots p_n^{a_n}$
  • 4

Readings 9

09NumberTheoryIII.pdf