ยง2.1 Exercises

Exercises 2.1.A

Exercise 2.1.1

Show that \(a^{p-1} \equiv 1 \pmod{p}\) for the given \(p\) and \(a\):

  • (a) \(a = 2, p = 5\)
  • (b) \(a = 4, p = 7\)
  • (c) \(a = 3, p = 11\)

Exercise 2.1.2

(a) If \(k \equiv 1 \pmod{4}\), then what is \(6k + 5\) congruent to modulo 4?

(b) If \(r \equiv 3 \pmod{10}\) and \(s \equiv -7 \pmod{10}\), then what is \(2r + 3s\) congruent to modulo 10?

Exercise 2.1.3

Every published book has a ten-digit ISBN-10 number (on the back cover or the copyright page) that is usually of the form \(x_1x_2x_3x_4x_5x_6x_7x_8x_9-x_{10}\) (where each \(x_i\) is a single digit).

The first 9 digits identify the book. The last digit \(x_{10}\) is a check digit; it is chosen so that:

\(10x_1 + 9x_2 + 8x_3 + 7x_4 + 6x_5 + 5x_6 + 4x_7 + 3x_8 + 2x_9 + x_{10} \equiv 0 \pmod{11}.\)

If an error is made when scanning or keying an ISBN number into a computer, the left side of the congruence will not be congruent to 0 modulo 11, and the number will be rejected as invalid.

Which of the following are apparently valid ISBN numbers?

  • (a) 3-540-90518-9
  • (b) 0-031-10559-5
  • (c) 0-385-49596-X

Exercise 2.1.4

Virtually every item sold in a store has a 12-digit UPC barcode which is scanned at the checkout counter. The first 11 digits of a UPC number \(d_1d_2d_3 \dots d_{11}d_{12}\) identify the manufacturer and product. The last digit \(d_{12}\) is a check digit chosen so that:

\(3d_1 + d_2 + 3d_3 + d_4 + 3d_5 + d_6 + 3d_7 + d_8 + 3d_9 + d_{10} + 3d_{11} + d_{12} \equiv 0 \pmod{10}.\)

Which of the following UPC numbers were scanned incorrectly?

  • (a) 037000356691
  • (b) 833732000625
  • (c) 040293673034

Exercise 2.1.5

(a) Which of \([0]\), \([1]\), \([2]\), \([3]\) is equal to \([5^{2000}]\) in \(\mathbb{Z}_4\)? [Hint: \(5 \equiv 1 \pmod{4}\); use Theorems 2.2 and 2.3.]

(b) Which of \([0]\), \([1]\), \([2]\), \([3]\), \([4]\) is equal to \([4^{200}]\) in \(\mathbb{Z}_5\)?

Exercise 2.1.6

If \(a \equiv b \pmod{n}\) and \(k \mid n\), is it true that \(a \equiv b \pmod{k}\)? Justify your answer.

Exercise 2.1.7

If \(a \in \mathbb{Z}\), prove that \(a^2\) is not congruent to 2 modulo 4 or to 3 modulo 4.

Exercise 2.1.8

Prove that every odd integer is congruent to 1 modulo 4 or to 3 modulo 4.

Exercise 2.1.9

Prove that:

  • (a) \((n - a)^2 \equiv a^2 \pmod{n}\)
  • (b) \((2n - a)^2 \equiv a^2 \pmod{4n}\)

Exercise 2.1.10

If \(a\) is a nonnegative integer, prove that \(a\) is congruent to its last digit mod 10. [For example, \(27 \equiv 7 \pmod{10}\).]

Exercises 2.1.B

Exercise 2.1.11

If \(a, b\) are integers such that \(a \equiv b \pmod{p}\) for every positive prime \(p\), prove that \(a = b\).

Exercise 2.1.12

If \(p \geq 5\) and \(p\) is prime, prove that \([p] = [1]\) or \([p] = [5]\) in \(\mathbb{Z}_6\). [Hint: Theorem 2.3 and Corollary 2.5.]

Exercise 2.1.13

Prove that \(a \equiv b \pmod{n}\) if and only if \(a\) and \(b\) leave the same remainder when divided by \(n\).

Exercise 2.1.14

(a) Prove or disprove: If \(ab \equiv 0 \pmod{n}\), then \(a \equiv 0 \pmod{n}\) or \(b \equiv 0 \pmod{n}\).

(b) Do part (a) when \(n\) is prime.

Exercise 2.1.15

If \((a, n) = 1\), prove that there is an integer \(b\) such that \(ab \equiv 1 \pmod{n}\).

Exercise 2.1.16

If \([a] = [1]\) in \(\mathbb{Z}_n\), prove that \((a, n) = 1\). Show by example that the converse may be false.

Exercise 2.1.17

Prove that \(10^n \equiv (-1)^n \pmod{11}\) for every positive \(n\).

Exercise 2.1.18

Use congruences (not a calculator) to show that \((125698)(23797) \neq 2891235306\). [Hint: See Exercise 21.]

Exercise 2.1.19

Prove or disprove: If \([a] = [b]\) in \(\mathbb{Z}_n\), then \((a, n) = (b, n)\).

Exercise 2.1.20

(a) Prove or disprove: If \(a^2 \equiv b^2 \pmod{n}\), then \(a \equiv b \pmod{n}\) or \(a \equiv -b \pmod{n}\).

(b) Do part (a) when \(n\) is prime.

Exercise 2.1.21

(a) Show that \(10^n \equiv 1 \pmod{9}\) for every positive \(n\).

(b) Prove that every positive integer is congruent to the sum of its digits mod 9 [for example, \(38 \equiv 11 \pmod{9}\)].

Exercise 2.1.22

(a) Give an example to show that the following statement is false: If \(ab \equiv ac \pmod{n}\) and \(a \not\equiv 0 \pmod{n}\), then \(b \equiv c \pmod{n}\).

(b) Prove that the statement in part (a) is true whenever \((a, n) = 1\).