5.6: Exercises

Exercise \(\PageIndex{1}\)

1. Let \(m > 0\). Show that \(a = _{m} b\) is an equivalence relation on \(\mathbb{Z}\). (Use Definitions 1.5 and 1.24.)
2. Describe the equivalence classes of \(\mathbb{Z}\) modulo \(6\). (Which numbers in \(\mathbb{Z}\) are equivalent to \(0\)? Which are equivalent to \(1\)? Et cetera.)
3. Show that the equivalence classes are identified by their residue, that is: \(a \sim b\) if and only if \(\mbox{Res}_{m} (a) = \mbox{Res}_{m} (b)\).

Note: If we pick one element of each equivalence class, such an element is called a representative of that class. The smallest non-negative represen- tative of a residue class in \(\mathbb{Z}_{m}\), is called the least residue. The collection consisting of the smallest non-negative representative of each residue class is called a complete set of least residues.

Exercise \(\PageIndex{2}\)

This exercise relies on exercise 5.1. Denote the set of equivalence classes of \(\mathbb{Z}\) modulo \(m\) by \(\mathbb{Z}_{m}\) (see Definition 1.5). Prove that addition and multiplication are well-defined in \(\mathbb{Z}_{m}\), using the following steps.

1. If \(a = _{m} a′\) and \(b = _{m} b′\), then \(\mbox{Res}_{m} (a) + \mbox{Res}_{m} (b) = _{m} \mbox{Res}_{m} (a′) + \mbox{Res}_{m} (b′)\). (Hint: show that \(a+b = c\) if and only if \(a+b = _{m} c\). In other words: the sum modulo \(m\) only depend on \(\mbox{Res}_{m} (a)\) and \(\mbox{Res}_{m} (b)\) and not on which representative in the class (see exercise 5.1) you started with.)
2. Do the same for multiplication.

Exercise \(\PageIndex{3}\)

Let \(n = \sum^{k}_{i=1} a_{i} 10^{i}\) where \(a_{i} \in \{0, 1, 2, \cdots ,9\}\).

1. Show that \(10^{k} = _{3} 1\) for all \(k \ge 0\). (Hint: use exercise 5.2.)
2. Show that \(n = 3 \sum^{k}_{i=1} a_{i}\).
3. Show that this implies that \(n\) is divisible by \(3\) if and only the sum of its digits is divisible by \(3\).

Exercise \(\PageIndex{4}\)

Let \(n = \sum^{k}_{i=1} a_{i} 10^{i}\) where \(a_{i} \in \{0, 1, 2, \cdots ,9\}\). Follow the strategy in exercise 5.3 to prove the following facts.

1. Show that \(n\) is divisible by \(5\) if and only if \(a_{0}\) is. (Hint: Show that \(n = _{5} a_{0}\).)
2. Show that \(n\) is divisible by \(2\) if and only if \(a_{0}\) is.
3. Show that \(n\) is divisible by \(9\) if and only if \(\sum^{k}_{i=1} a_{i}\) is.
4. Show that \(n\) is divisible by \(11\) if and only if \(\sum^{k}_{i=1} (-1)^{i} a_{i}\) is.
5. Find the criterion for divisibility by \(4\).
6. Find the criterion for divisibility by \(7\). (Hint: this is a more complicated criterion!)

Exercise \(\PageIndex{5}\)

1. List \((n-1)!\) mod \(n\) for \(n \in \{2, \cdots, 16\}\).
2. Where does the proof of the first part of Wilson’s theorem fail in the case of \(n = 16\)?
3. Does Wilson’s theorem hold for \(p = 2\)? Explain!

Exercise \(\PageIndex{6}\)

Denote by \(\{x_{i}\}\) the reduced set of residues modulo \(16\). If the reasoning similar to that of Wilson’s theorem holds, you expect that \(\prod_{i} x_{i} = _{16} -1\).

1. Compute \(\prod_{i} x_{i}\).
2. How does the reasoning in Wilson’s theorem fail? (Hint: see lemma 5.17.)
3. List the product of the reduced set of residues modulo \(n\) for \(n \in \{2, \cdots ,16\}\).

Exercise \(\PageIndex{7}\)

1. For \(i\) in \(\{1,2, \cdots 11\}\) and \(j\) in \(\{2,3, \cdots 11\}\), make a table of \(\mbox{Ord}^{\times}_{j} (i)\), \(i\) varying horizontally. After the jth column, write \(\varphi (j)\).
2. List the primitive roots \(i\) modulo \(j\) for \(i\) and \(j\) as in (a). (Hint: the smallest primitive roots modulo \(j\) are: \(\{1,2,3,2,5,3, \emptyset, 2,3,2\}\).)

Exercise \(\PageIndex{8}\)

1. Determine the period of the decimal expansion of the following numbers: \(100/13, 13/77\), and \(1/17\) through long division.
2. Use Proposition 5.6 to determine the period.
3. Check that this period equals a divisor of \(\varphi (n)\).
4. The same questions for expansions in base \(2\) instead of base \(10\).

Exercise \(\PageIndex{9}\)

1. Compute \(2^{n-1}\) mod \(n\) for \(n\) odd in \(\{3 \dots 40\}\).
2. Are there any pseudo-primes in the list?

Exercise \(\PageIndex{10}\)

Assume that \(n\) is a pseudoprime to the base \(2\).

1. Show that \(2^{n}-2 = _{n} 0\).
2. Show from (a) that \(n | M_{n}-1\). (See Definition 5.11.)
3. Use Lemma 5.12 to show that (b) implies that \(M_{n}| 2^{M_{n}-1}-1\).
4. Conclude from (c) that if \(n\) is a pseudoprime in base \(2\), so is \(M_{n}\).

Exercise \(\PageIndex{11}\)

We show that the 5-th Fermat number, \(2^{32}+1\), is a composite number.

1. Show that \(2^{4} = _{641} -5^4\). (Hint: add \(2^4\) and \(5^4\).)
2. Show that \(2^{75} = _{641} -1\).
3. Show that \(2^{32} +1 = (2^{7})^{4} 2^{4}+1 = _{641} 0\).
4. Conclude that \(F_{5}\) is divisible by \(641\).

Exercise \(\PageIndex{12}\)

1. Compute \(\varphi (100)\). (Hint: use Theorem 4.16.)
2. Show that \(179^{121} = _{100} 79^{121}\).
3. Show that \(79^{121} = _{100} 79^{1}\). (Hint: use Theorem 5.4)
4. What are the last \(2\) digits of \(179^{121}\)?

The following 5 exercises on basic cryptography are based on [22]. First some language. The original readable message is called the plain text. Encoding the message is called encryption. And the encoded message is often called the encrypted message or code. To revert the process, that is: to turn the encrypted message back into plain text, you often need a key. Below we will encode the letters by \(0\) through \(25\) (in alphabetical order). We encrypt by using a multiplicative cipher. This means that we will encrypt our text by multiplying each number by the cipher modulo 26, and then return the corresponding letter. For example, if we use the cipher \(3\) to encrypt the plain text bob, we obtain the encrypted text as follows 1.14.1 \(\rightarrow\) 3.42.3 \(\rightarrow\) 3.16.3.

Exercise \(\PageIndex{13}\)

1. Use the multiplicative cipher \(3\) to decode DHIM.
2. Show that an easy way to decode is multiplying by \(9\) (modulo \(26\)). The corresponding algorithm at the number level is called division by \(3\) modulo \(26\).
3. Suppose instead that our multiplicative cipher was \(4\). Encode bob again.
4. Can we invert this encryption by using multiplication modulo \(26\)? Explain why.

Exercise \(\PageIndex{14}\)

Suppose we have an alphabet of \(q\) letters and we encrypt using the multiplicative cipher \(p \in \{0, \cdots q-1\}\). Use modular arithmetic to show that the encryption can be inverted if and only \(\gcd (p, q) = 1\). (Hint: Assume the encryption of \(j_{1}\) and \(j_{2}\) are equal. Then look up and use the Unique Factorization theorem in Chapter 2.)

Exercise \(\PageIndex{15}\)

Assume the setting of exercise 5.14. Assume \(p\) and \(q\) are such that the encryption is invertible. What is the decryption algorithm? Prove it. (Hint Find \(r \in \{0, \cdots q-1\}\) such that \(rp = _{q} 1\). Then multiply the encryption by \(r\).)

Exercise \(\PageIndex{16}\)

Work out the last two problems if we encrypt using an affine cipher \((a, p)\). That is, the encryption on the alphabet \(\{0, \cdots q-1\}\) is done as follows:

\[i \rightarrow a+pi \mbox{ mod } q \nonumber\]

Work out when this can be inverted, and what the algorithm for the inverse is.

Exercise \(\PageIndex{17}\)

Decrypt the code V’ir Tbg n Frperg.

Exercise \(\PageIndex{18}\)

1. Compute \(7^{72}\) mod \(13\), using modular exponentiation.
2. Similarly for \(484^{187}\) mod \(1189\).
3. Find \(100!+102!\) mod \(101\). (Hint: Fermat.)
4. Show that \(1381! = _{1382} 0\). (Hint: Wilson.)

Exercise \(\PageIndex{19}\)

Characterize the set of \(n \ge 2\) for which \((n-1)!\) mod \(n\) is not in \(\{0, -1\}\). (Hint: Wilson.)

Theorem 5.20 (Binomial Theorem)

If \(n\) is a positive integer, then

\[\begin{array}{ccc} {(a+b)^{n} = \sum_{i=0}^{n} \binom{n}{i} a^{i} b^{n-i}}&{\mbox{where}}&{\binom{n}{i} = \frac{n!}{i! (n-i)!}} \end{array} \nonumber\]

Exercise \(\PageIndex{20}\)

1. If \(p\) is prime, show that \({p \choose i}\) mod \(p\) equals \(0\) if \(1 \le i \le p-1\), and equals \(1\) if \(i = 0\) or \(i = p\).
2. Evaluate \({4 \choose 2} \mbox{ mod } 4\) and \({6 \choose 4} \mbox{ mod } 6\). So, where in (a) did you use the fact that \(p\) is prime?
3. Use the binomial theorem to show that if \(p\) is prime \((a+b)^{p} = _{p} a^{p}+b^{p}\)

Exercise \(\PageIndex{21}\)

Let \(p\) be prime.

1. Show that \(0^{p} = _{p} 0\)
2. Show that for \(k > 0\), if \(k^{p} = _{p} k\), then \((k+1)^{p} = _{p} k+1\). (Hint: use exercise 5.20.)
3. Conclude that for all \(n \in \{0,1,2,\cdots\}, n^{p} = _{p} n\). (Hint: use induction)
4. Prove that for all \(n \in \mathbb{Z}, n^{p} = _{p} n\). (Hint: \((-n)^{p} = _{p} (-1)^{p}n^{p}\).)
5. Use (d) to prove Fermat's Little Theorem. (Hint: use cancellation.)

Exercises 3.19 and 3.22 show how to solve linear congruences generally. Quadratic congruences are much more complicated. As an example. we look at the equation \(x^{2} = _{p} \pm 1\) in the following exercise.

Exercise \(\PageIndex{22}\)

1. Show that Fermat's little theorem gives a solution of \(x^{2}-1 = _{p} 0\) whenever \(p\) is an odd prime. (Hint: consider \(a^{\frac{p-1}{2}}\).)
2. Show that Wilson's theorem implies that for odd primes \(p\) \[(-1)^{\frac{p-1}{2}} ((\frac{p-1}{2})!)^2 = _{p} -1 \nonumber\] (hint: the right hand gives all reduced residues module \(p\).)
3. Show that if also \(p = _{4} 1\) (examples are 13,17,29, etc), then \[((\frac{p-1}{2})!)^2 = _{p} -1 \nonumber\] satisfies the quadratic congruence \(x^2+1 = _{p} 0\).
4. Suppose \(x^2+1 = _{p} 0\) and \(p\) is an odd prime. Show that Fermat's little theorem implies that \[(-1)^{\frac{p-1}{2}} = 1 \nonumber\]
5. Show that \(p\) in (d) cannot satisfy \(p = _{4} 3\).

Exercise \(\PageIndex{23}\)

Let \(R = \{1,3,5,7,9,11,13,15\}\), the reduced set of residues module \(16\). In \(\mathbb{Z}_{16}\) and for each \(r \in R\), define multiplication by \(r^{-1}\) (or division by \(r\)).

Exercise \(\PageIndex{24}\)

1. Draw up the addition and multiplication tables for \(\mathbb{Z}_{7}\).
2. Do the same for \(\mathbb{Z}_{8}\). Is division well-defined.
3. The same for the reduced set of residues plus \(0\) in \(\mathbb{Z}_{8}\). What goes wrong here?

Exercise \(\PageIndex{25}\)

Given \(n > 2\), let \(R \subseteq \mathbb{Z}_{n}\) be the reduced set of residues and let \(S \subseteq \mathbb{Z}_{n}\) be the set of solutions in \(\mathbb{Z}_{n}\) of \(x^{2} = _{n} 1\) (or self inverses).

1. Show that \(S \subseteq R\). (Hint:Be ́zout)
2. Show that \[\prod_{x \in R} x = n \prod_{x \in S} x (= _{n} 1 \mbox{ if S is empty}) \nonumber\]
3. Show that if \(S\) contains \(a\), then it contains \(-a\).
4. Show that if \(a = _{n} -a\), then \(a\) and \(-a\) are not in \(S\).
5. Show that \[\begin{array} {cc} {\prod_{x \in R} x = _{n} (-1)^m}&{\mbox{some } m} \end{array} \nonumber\]
6. Show that \(m = |S|/2\).