Skip to main content

Exercises 3.4 Exercises

1.

Find all \(x \in {\mathbb Z}\) satisfying each of the following equations.

  1. \(\displaystyle 3x \equiv 2 \pmod{7}\)

  2. \(\displaystyle 5x + 1 \equiv 13 \pmod{23}\)

  3. \(\displaystyle 5x + 1 \equiv 13 \pmod{26}\)

  4. \(\displaystyle 9x \equiv 3 \pmod{5}\)

  5. \(\displaystyle 5x \equiv 1 \pmod{6}\)

  6. \(\displaystyle 3x \equiv 1 \pmod{6}\)

2.

Show that

\begin{equation*} 0 + a \equiv a + 0 \equiv a \pmod{ n } \end{equation*}

for all \(a \in {\mathbb Z}_n\text{.}\)

3.

Prove that there is a multiplicative identity for the integers modulo \(n\text{,}\) meaning that:

\begin{equation*} a \cdot 1 \equiv a \pmod{n}. \end{equation*}

4.

For each \(a \in {\mathbb Z}_n\) find an element \(b \in {\mathbb Z}_n\) such that

\begin{equation*} a + b \equiv b + a \equiv 0 \pmod{ n}. \end{equation*}

5.

Show that addition and multiplication mod \(n\) are well defined operations. That is, show that the operations do not depend on the choice of the representative from the equivalence classes mod \(n\text{.}\)

6.

Show that addition and multiplication mod \(n\) are associative operations:

\begin{align*} (a + b) + c & \equiv a + (b + c)\pmod{ n}\\ (a b) c & \equiv a (b c) \pmod{ n}. \end{align*}

7.

Show that multiplication distributes over addition modulo \(n\text{:}\)

\begin{equation*} a(b + c) \equiv ab + ac \pmod{n}. \end{equation*}

8.

Use the corollary to Fermat's Little Theorem to show that if \(p = 4n + 3\) is prime, there is no solution to the equation \(x^2 \equiv -1 \pmod{p}\text{.}\)

9.

Is ISBN 0-534-91500-0 a valid ISBN-10 code? What about ISBN 0-534-91700-0 and ISBN 0-534-19500-0?

10. UPC Symbols.

Universal Product Code (UPC) symbols are found on most products in grocery and retail stores. The UPC symbol is a 12-digit code identifying the manufacturer of a product and the product itself (Figure 3.16). The first 11 digits contain information about the product; the twelfth digit is used for error detection. If \(d_1 d_2 \cdots d_{12}\) is a valid UPC number, then

\begin{equation*} 3 \cdot d_1 + 1 \cdot d_2 + 3 \cdot d_3 + \cdots + 3 \cdot d_{11} + 1 \cdot d_{12} \equiv 0 \pmod{10}. \end{equation*}

  1. Show that the UPC number 0-50000-30042-6, which appears in Figure 3.16, is a valid UPC number.

  2. Show that the number 0-50000-30043-6 is not a valid UPC number.

  3. Write a formula to calculate the check digit, \(d_{12}\text{,}\) in the UPC number.

  4. The UPC error detection scheme can detect most transposition errors; that is, it can determine if two digits have been interchanged. Show that the transposition error 0-05000-30042-6 is not detected. Find a transposition error that is detected. Can you find a general rule for the types of transposition errors that can be detected?

  5. Write a program that will determine whether or not a UPC number is valid.

Figure 3.16. A UPC code

11.

The 10-digit ISBN allowed too few possibilities, so it was extended by 3 digits ISBN-13. ISBN-13 uses a mod 10 check digit, similar to the UPC code. Any ISBN-10 can be converted into an ISBN-13 by prefixing the digits 978 and recomputing the check digit. Design an alternative mod 11 check digit system called ISBN-13alt and a prefix that can added to any valid ISBN-10 to make a valid ISBN-13alt. Does your system detect all changed digits and all transpositions?

12.

It is often useful to use an inner product notation for this type of error detection scheme; hence, we will use the notion

\begin{equation*} (d_1, d_2, \ldots, d_k ) \cdot (w_1, w_2, \ldots, w_k ) \equiv 0 \pmod{ n } \end{equation*}

to mean

\begin{equation*} d_1 w_1 + d_2 w_2 + \cdots + d_k w_k \equiv 0 \pmod{ n}. \end{equation*}

Suppose that \((d_1, d_2, \ldots, d_k ) \cdot (w_1, w_2, \ldots, w_k ) \equiv 0 \pmod{ n}\) is an error detection scheme for the \(k\)-digit number \(d_1 d_2 \cdots d_k\text{,}\) where \(0 \leq d_i \lt n\text{.}\) Prove that all single-digit errors are detected if and only if \(\gcd( w_i, n ) = 1\) for \(1 \leq i \leq k\text{.}\)

13.

Let \((d_1, d_2, \ldots, d_k ) \cdot (w_1, w_2, \ldots, w_k ) \equiv 0 \pmod{ n}\) be an error detection scheme for the \(k\)-digit identification number \(d_1 d_2 \cdots d_k\text{,}\) where \(0 \leq d_i \lt n\text{.}\) Prove that all transposition errors of two digits \(d_i\) and \(d_j\) are detected if \(\gcd( w_i - w_j, n ) = 1\) for \(i\) and \(j\) between \(1\) and \(k\text{.}\)

14.

Prove that there doesn't exist a check digit system modulo \(n=10\) with \(k \geq 2\) digits which will detect all single-digit errors and all transpositions.

15.

Solve each of the following systems of congruences.

  1. \begin{align*} x & \equiv 2 \pmod{5}\\ x & \equiv 6 \pmod{11} \end{align*}
  2. \begin{align*} x & \equiv 3 \pmod{7}\\ x & \equiv 0 \pmod{8}\\ x & \equiv 5 \pmod{15} \end{align*}
  3. \begin{align*} x & \equiv 2 \pmod{4}\\ x & \equiv 4 \pmod{7}\\ x & \equiv 7 \pmod{9}\\ x & \equiv 5 \pmod{11} \end{align*}
  4. \begin{align*} x & \equiv 3 \pmod{5}\\ x & \equiv 0 \pmod{8}\\ x & \equiv 1 \pmod{11}\\ x & \equiv 5 \pmod{13} \end{align*}

16.

Use the method of parallel computation outlined in the text to calculate \(2234 + 4121\) by dividing the calculation into four separate additions modulo 95, 97, 98, and 99.

17.

Explain why the method of parallel computation outlined in the text fails for \(2134 \cdot 1531\) if we attempt to break the calculation down into two smaller calculations modulo 98 and 99.