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, \ldots, 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}) \mmod{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 \Mod{5}\)
2. \(\displaystyle 4x \equiv 3 \Mod{5}\)
3. \(\displaystyle 2x \equiv 10 \Mod{8}\)
4. \(\displaystyle 33x + 4 \equiv 2 \Mod{7}\)
5. \(\displaystyle 100x - 23 \equiv 11 \Mod{99}\)
6. \(\displaystyle 31 - 11x \equiv 4x + 8 \Mod{44}\)

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,\ldots,a_{\phi(n)}\) are the \(\phi(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 \Mod{n}\) has no solutions.

15.

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

16.

If \(m = 2^k\) is a power of 2, explain how you could use repeated squaring to compute \(a^m \mmod{n}\) for any \(n\text{.}\) Then apply your method to compute \(10^{32} \mmod 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 \mmod{n}\)for any \(n\text{.}\) Then apply your method to compute \(17^{26} \mmod 44\text{.}\)

18.

Prove \(\phi(p^kq^l) = \left(p^k-p^{k-1}\right)\left(q^l - q^{l-1}\right)\) 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 \(\phi(m)\) 4.4.1 is a multiplicative function. (The proof uses Section 4.5.)

1. Give a general formula for \(\phi(p_1^{r_1}p_2^{r_2}\cdots p_k^{r_k})\) where the \(p_i\)'s are distinct primes.
2. Compute \(\phi(9000)\) and \(\phi(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} \mmod{5}\)
2. \(\displaystyle 2^{2020} \mmod{7}\)
3. \(\displaystyle 2^{2020} \mmod{11}\)
4. \(\displaystyle 2^{2020} \mmod{385}\)