Solutions to Problem Set 23

Math 310-01/02

11-8-2017

1. Simplify the following expressions. Your answers should be in the range $\{0, 1, 2, \ldots, 10\}$ .

(a) $3 \cdot 9 + 8^2 \mod{11}$ .

(b) $-(6 \cdot 3) \mod{11}$ .

(c) $12^{1403} \mod{11}$ .

(a)

$$3 \cdot 9 + 8^2 = 27 + 64 = 91 = 3 \mod{11}.\quad\halmos$$

(b)

$$-(6 \cdot 3) = -18 = 4 \mod{11}.\quad\halmos$$

(c)

$$12^{1403} = 1^{1403} = 1 \mod{11}.\quad\halmos$$


2. If $x \in \{0, 1, 2, \ldots, n
   - 1\}$ , the multiplicative inverse of x mod n is denoted $x^{-1} \mod{n}$ . It is the number (if there is one) which satisfies the equations

$$x \cdot x^{-1} = 1 \mod{n} \quad\hbox{and}\quad x^{-1} \cdot x = 1 \mod{n}.$$

(a) Find $4^{-1} \mod{7}$ . Your answer should be in the range $\{0, 1, 2, \ldots, 6\}$ .

(b) Show that 4 does not have a multiplicative inverse mod 6.

(a) Since $4 \cdot 2 = 8 = 1
   \mod{7}$ , it follows that $4^{-1} = 2 \mod{7}$ .

(b) One approach is to try all the numbers in $\{0, 1, 2, 3, 4, 5\}$ :

$$0 \cdot 4 = 0 \mod{6}, \quad 1 \cdot 4 = 4 \mod{6}, \quad 2 \cdot 4 = 2 \mod{6},$$

$$3 \cdot 4 = 0 \mod{6}, \quad 4 \cdot 4 = 4 \mod{6}, \quad 5 \cdot 4 = 2 \mod{6}.$$

Alternatively, you can give a proof by contradiction. Suppose $4 x = 1 \mod{6}$ . Multiply both sides by 3:

$$\eqalign{ 3 \cdot 4 x & = 3 \cdot 1 \mod{6} \cr 12 x & = 3 \mod{6} \cr 0 & = 3 \mod{6} \cr}$$

The last line is a contradiction, and so there is no number x such that $4 x = 1 \mod{6}$ .


3. Use modular arithmetic to prove that if $x \in \integer$ , then $x^2 + 3
   x + 4$ is not divisible by 5.

If $x \in \integer$ , then $x = 0$ , 1, 2, 3, or 4 mod 5. I take cases:

$$\vbox{\offinterlineskip \halign{& \vrule # & \strut \hfil \quad # \quad \hfil \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr & $x \mod{5}$ & & 0 & & 1 & & 2 & & 3 & & 4 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr & $x^2 + 3 x + 4 \mod{5}$ & & 4 & & 3 & & 4 & & 2 & & 2 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} }} $$

For all x I have $x^2 + 3 x + 4
   \ne 0 \mod{5}$ . It follows that if $x \in \integer$ , then $x^2 + 3 x + 4$ is not divisible by 5.


4. Give specific values of $a,
   b, c \in \integer$ and $n \in \integer$ with $n \ge 2$ to show that the following statement is false:

"If $b = c \mod{n}$ , then $a^b = a^c \mod{n}$ ."

Take $a = 2$ , $b = 1$ , $c = 6$ , and $n = 5$ . Then $1 = 6
   \mod{5}$ . However, $2^1 = 1$ and $2^6 = 64$ , and $1 \ne 64 \mod{5}$ .


Nothing is so exhausting as indecision, and nothing is so futile. - Bertrand Russell


Contact information

Bruce Ikenaga's Home Page

Copyright 2017 by Bruce Ikenaga