Exercises

Exercises 4.7 Exercises

Additional Exercises for Chapter 4

1.

Let

\begin{equation*} R = \{(1,1),(2,2),(1,2),(2,1),(1,3),(3,3),(3,1),(4,4)\} \end{equation*}

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

\begin{equation*} f \star g \Leftrightarrow f'(x) = g'(x)\text{.} \end{equation*}

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

3.

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

\begin{equation*} m \sim n \Leftrightarrow 4 \mid (m^2 - n^2)\text{.} \end{equation*}

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

\begin{equation*} R = \{(x,y) : x \text{ and } y \text{ are in the same $A_i$}\} \end{equation*}

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

$3^{333}$ is divided by $100$
$5^{444}$ is divided by $11$
$2^{888}$ is divided by $8$
$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{:}$

$\displaystyle b = 4, n = 5$
$\displaystyle b = 13, n = 76$
$\displaystyle b = 33, n = 7$
$\displaystyle b = 10, n = 9$
$\displaystyle b = 100, n = 999$

11.

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

$\displaystyle 4x \equiv 8 \Mod{5}$
$\displaystyle 4x \equiv 3 \Mod{5}$
$\displaystyle 2x \equiv 10 \Mod{8}$
$\displaystyle 33x + 4 \equiv 2 \Mod{7}$
$\displaystyle 100x - 23 \equiv 11 \Mod{99}$
$\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.7.12 to argue that

\begin{equation*} a_1 + a_2 + \cdots + a_{\phi(n)} \equiv 0 \Mod{n}\text{.} \end{equation*}

Hint

For example, if $n = 8\text{,}$ then the sum of the units modulo $8$ is $1 + 3 + 5 + 7 \equiv 0 \Mod{8}\text{.}$

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{.}$

Hint

Every natural number can be written as the sum of powers of two.

17.

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

Hint

Express $m$ as a sum of powers of two.

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{.}$

Hint

Checkpoint 4.4.7 and Checkpoint 4.4.8.

19.

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

\begin{equation*} f(mn) = f(m)f(n) \end{equation*}

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.)

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.
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

\begin{equation*} \begin{cases} x \equiv 2 \Mod{3} \\ x \equiv 2 \Mod{7} \\ x \equiv 1 \Mod{13} \end{cases} \end{equation*}

using the method outlined in Theorem 4.5.6.

22.

Compute each quantity:

$\displaystyle 2^{2020} \mmod{5}$
$\displaystyle 2^{2020} \mmod{7}$
$\displaystyle 2^{2020} \mmod{11}$
$\displaystyle 2^{2020} \mmod{385}$

Hint

$385 = 5 \cdot 7 \cdot 11\text{.}$

23.

Your friend has been boasting about getting an A in their cryptography course, and now refuses to reply to any messages that are not encrypted using their RSA public key ($N = 77$ and $e = 19$).

You want to send the message WEIRDFLEX to your friend.

Encode the message as two-digit blocks, one block for each letter. (e.g.W is 23, etc.)
Encrypt the message using your friend's public key.
Your friend might not have deserved that A, since they picked $N$ to be easily factorable. Determine your friend's private key, then decrypt the message you sent them.

24.

You want to get back at your friend from Exercise 4.7.23 by using the RSA system to receive messages as well.

You pick $p = 53$ and $q = 61\text{,}$ so that $N = 3233\text{,}$ and you pick $e = 121\text{.}$

Determine your decryption key $d\text{.}$
You receive the message $0685 \ 1635 \ 0365$ from your friend, who grouped letters into blocks of two letters each. Decrypt the message and translate back into letters.

25.

Given each public key $(N,e)\text{,}$ find the decryption key $d\text{.}$

$N = 323\text{,}$ $e=11\text{.}$
$N = 138653\text{,}$ $e=65537\text{.}$