MAT202: Introduction to Discrete Mathematics

1.

Let

be a relation on the set $\{1,2,3,4\}\text{.}$ Is $R$ an equivalence relation? Which properties (reflexive, symmetric, transitive) hold/fail?

2.

Let $S$ be the set of differentiable functions from $\mathbb{R}$ to $\mathbb{R}\text{,}$ and let $\star$ be the relation

Is $\star$ an equivalence relation? If it is, describe its equivalence classes.

3.

Let $\sim$ be the following relation on $\mathbb{Z}\text{:}$

Is $\sim$ an equivalence relation? If it is, describe its equivalence classes.

4.

Let $A_1,A_2,\dots ,A_k$ form a partition of $S\text{.}$ Show that the relation

is an equivalence relation on $S\text{.}$

What are the equivalence classes of $R\text{?}$

5.

If $R$ is an equivalence relation on the set $S\text{,}$ and $a,b\in S$ such that $a\in [b]\text{,}$ show that $[a]=[b]\text{.}$ Do not use Lemma 4.1.9 or Theorem 4.1.10.

6.

Compute the remainder when

1. $3^{333}$ is divided by $100$
2. $5^{444}$ is divided by $11$
3. $2^{888}$ is divided by $8$
4. $9^{999}$ is divided by $99$

7.

Show that $(3+3^3+3^5+3^7+3^9+3^{11})\mathbf{mod}10=0\text{.}$

8. Winter 2018 Final.

Without using induction, prove that ${11}^{n+2}+{12}^{2n+1}$ is divisible by $133$ for any $n\in \mathbb{N}\text{.}$

9.

Let $N$ be the product of any $k$ consecutive natural numbers. Prove $k!\mid N\text{.}$

10.

Find the multiplicative inverse of each integer $b$ modulo $n\text{:}$

1. ${\displaystyle b=4,n=5}$
2. ${\displaystyle b=13,n=76}$
3. ${\displaystyle b=33,n=7}$
4. ${\displaystyle b=10,n=9}$
5. ${\displaystyle b=100,n=999}$

11.

Solve the following congruences. Express your answer as congruence classes of the original modulus.

1. ${\displaystyle 4x\equiv 8\left(\mathrm{mod}5\right)}$
2. ${\displaystyle 4x\equiv 3\left(\mathrm{mod}5\right)}$
3. ${\displaystyle 2x\equiv 10\left(\mathrm{mod}8\right)}$
4. ${\displaystyle 33x+4\equiv 2\left(\mathrm{mod}7\right)}$
5. ${\displaystyle 100x-23\equiv 11\left(\mathrm{mod}99\right)}$
6. ${\displaystyle 31-11x\equiv 4x+8\left(\mathrm{mod}44\right)}$

12.

If $a$ is a unit modulo $n\text{,}$ show that $-a$ is also a unit modulo $n\text{.}$ (See Definition 4.3.8)

13.

Suppose that $a_1,a_2,\dots ,a_{\varphi (n)}$ are the $\varphi (n)$ units modulo $n\text{.}$ Use Exercise 4.6.12 to argue that

14.

Prove that if $gcd(a,n)\nmid b\text{,}$ then $ax\equiv b\left(\mathrm{mod}n\right)$ has no solutions.

15.

Let $a\in \mathbb{N}$ and suppose $p$ is prime. Prove that $a^2\equiv 1\left(\mathrm{mod}p\right)$ if and only if $a\equiv 1\left(\mathrm{mod}p\right)$ or $a\equiv -1\left(\mathrm{mod}p\right)\text{.}$

16.

If $m=2^k$ is a power of 2, explain how you could use repeated squaring to compute $a^m\mathbf{mod}n$ for any $n\text{.}$ Then apply your method to compute ${10}^{32}\mathbf{mod}41\text{.}$

17.

If $m$ is not a power of 2, explain how you could use the results of Exercise 4.6.16 to compute $a^m\mathbf{mod}n$for any $n\text{.}$ Then apply your method to compute ${17}^{26}\mathbf{mod}44\text{.}$

18.

Prove $\varphi (p^k{q}^l)=(p^k-p^{k-1})(q^l-q^{l-1})$ for primes $p$ and $q\text{,}$ and $k,l\in \mathbb{N}\text{.}$

19.

A function $f(n)$ on the integers is said to be multiplicative if

whenever $gcd(m,n)=1\text{.}$ Euler's Totient Function $\varphi (m)$ 4.4.1 is a multiplicative function. (The proof uses Section 4.5.)

1. Give a general formula for $\varphi (p_1^{r_1}{p}_2^{r_2}\cdots p_k^{r_k})$ where the $p_i$'s are distinct primes.
2. Compute $\varphi (9000)$ and $\varphi (133947)$

20.

Find the smallest positive integer $y$ such that

• $y$ divided by 9 leaves a remainder of 7, and
• $y$ divided by 10 leaves a remainder of 9.

21.

Solve the system of congruences

using the method outlined in Theorem 4.5.6.

22.

Compute each quantity:

1. ${\displaystyle 2^{2020}\mathbf{mod}5}$
2. ${\displaystyle 2^{2020}\mathbf{mod}7}$
3. ${\displaystyle 2^{2020}\mathbf{mod}11}$
4. ${\displaystyle 2^{2020}\mathbf{mod}385}$