Mathematics 243, section 2 – Mathematical Structures Solutions for Sample Exam Questions – Exam 2 October 30, 2017

I. Let [a] ∈ Z/18Z and let m_{[a]} : Z/18Z → Z/18Z be the mapping defined by m_{[a]}([x]) = [a] · [x] = [a · x]. A) Is m_{[12]} an injective mapping? Why or why not? Is it a surjective mapping? Why or

why not? Solution: The m_{[12]} is not an injective mapping because, for instance [x] = [0] and [x] = [3] satisfy

m_{[12]}([0]) = [0] = m_{[12]}([3])

but [0] ≠ [3] in Z/18Z. B) Is m_{[5]} an injective mapping? Why or why not?

Solution: Yes, m_{[5]} is an injective mapping. Note that gcd(5, 18) = 1, so [5] has a multiplicative inverse in Z/18Z. In fact, we can see that [5]^{−1} = [11] since [5] · [11] = [55] = [1] in Z/18Z. Hence, if [x] and [x′] are in Z/18Z and m_{[5]}([x]) = m_{[5]}([x′]), then

[5][x] = [5][x′], so
[11]([5][x]) = [11]([5][x′]), and hence
([11][5])[x] = ([11][5])[x′], by associativity, so
[1][x] = [1][x′], which shows
[x] = [x′].

This shows m_{[5]} is an injective mapping. C) Prove that m_{[a]} is injective if and only if [a] has a multiplicative inverse in Z/18Z.

Solution: The proof that if a multiplicative inverse [a]^{−1} exists in Z/18Z, then m_{[a]} is injective is just the same as the proof given for the case a = 5 in part B. For the converse, suppose that m_{[a]} is injective. Since m_{[a]} is injective, its range will contain 18 distinct elements of Z/18Z. But there are only 18 different elements in this structure: Z/18Z = {[0], [1], …, [17]}. Hence there must be an element [x] such that [a][x] = [1]. This shows that [a] has a multiplicative inverse.

D) Prove the m_{[a]} is injective if and only if m_{[a]} is surjective.

Solution: The proof that m_{[a]} injective implies it is also surjective is the same as part of the proof for part C: If m_{[a]} is injective, then its range contains exactly 18 distinct elements in Z/18Z. But there are only 18 distinct elements altogether, so the range must consist of all of Z/18Z, and that shows the mapping is surjective. Conversely, if the mapping m_{[a]} is surjective, then there must be 18 different elements in the range. But since the domain consists of only 18 elements altogether, then those elements of the domain must map to 18 distinct images. (Alternatively, in the contrapositive form, if m_{[a]} is not injective, then two distinct elements of the domain must map to the same element in Z/18Z. But that means there are no more than 17 distinct elements in the range, so the range cannot be all of Z/18Z and the mapping is not surjective.)

II.

A) Given integers a, and b > 0, prove that there exist unique integers q and r such that a = qb + r and 0 ≤ r < b. (You may apply the Well-Ordering Principle without justifying that.) Solution: See class notes and/or Theorem 4.8 in the text.

B) Find the quotient q and the remainder r as in part A for a = 4578 and b = 235. Solution: q = 19 and r = 113.

III. A) Prove that if S = ⟨a, b⟩ = {x ∈ Z : x = ma + nb, m, n ∈ Z}, then the smallest positive

integer d in S satisfies the properties:

1. d divides a and d divides b.

Solution: We claim that in fact d divides every element of ⟨a, b⟩. This will imply the required statement since a = 1 · a + 0 · b and b = 0 · a + 1 · b are both elements of ⟨a, b⟩. So let x = ma + nb, m, n ∈ Z, be any element of ⟨a, b⟩ and divide x by d using the division algorithm: x = qd + r where 0 ≤ r < d. Now we have d = m_{0}a + n_{0}b for some m_{0}, n_{0} ∈ Z. Hence

r = x − qd = ma + nb − q(m_{0}a + n_{0}b) = (m − qm_{0})a + (n − qn_{0})b

Now m − qm_{0} and n − qn_{0} are clearly in Z so by definition, r ∈ ⟨a, b⟩. But d was the smallest positive element in ⟨a, b⟩, so since 0 ≤ r < d, the only possibility is that r = 0. Hence d divides x.

2. If c divides a and c divides b, then c divides d. Solution: If c divides a and c divides b, then we have a = cs and b = ct for some integers s, t. But then because d = m_{0}a + n_{0}b, we can substitute to get

d = m_{0}cs + n_{0}ct = c(m_{0}s + n_{0}t).

Since m_{0}s + n_{0}t is clearly in Z, this shows c divides d. B) Find the integer d = gcd(488, 376) and express d in the form d = m · 488 + n · 76 for

integers m, n. Solution: By the Euclidean algorithm,

\begin{aligned}488 & = 1 · 376 + 112 \\ 376 & = 3 · 112 + 40 \\ 112 & = 2 · 40 + 32 \\ 40 & = 1 · 32 + 8 \end{aligned}

and 8 divides 32, so the final nonzero remainder is the gcd: gcd(488, 376) = 8. To find the required m, n, use the Extended Euclidean algorithm:

1 0 0 1

1 1 − 1
3 − 3 4
2 7 − 9
1 − 10 13

This gives the equation (−10) · (488) + (13) · (376) = 8. C) Prove that if there is a solution of the congruence ax ≡ b (mod n) (where n > 1),

then gcd(a, n)|b. Solution: If there is a solution x of the congruence ax ≡ b mod n, then ax − b = ny for some integer y. But this implies ax + n(−y) = b, so b ∈ ⟨a, n⟩ in Z. Since the gcd is the smallest positive element of ⟨a, n⟩, the argument given in the solution for III A above shows that gcd(a, n)|b.

IV. A) Show that for all n ≥ 1, 8|(9^{n} − 1). (Hint: Show first that 9^{k+1} − 1 = 9^{k} · 8 + (9^{k} − 1).)

Solution: We argue by mathematical induction on n. The base case is n = 1, and 8|(9 − 1) is clear because 9 − 1 = 8. For the induction step, suppose 8|(9^{k} − 1) and consider 9^{k+1} − 1. Note that

9^{k+1} − 1 = 9^{k} · 9 − 1 = 9^{k} · (8 + 1) − 1 = 9^{k} · 8 + 9^{k} − 1.

Now if 8|(9^{k} − 1) then we have 9^{k} − 1 = 8 · ℓ for some integer ℓ. Hence

9^{k+1} − 1 = 9^{k} · 8 + 8 · ℓ = 8 · (9^{k} + ℓ).

Since 9^{k} + ℓ ∈ Z, this shows 8|(9^{k+1} − 1), and the proof is complete. B) Restate the result of part A as a congruence.

Solution: The result from part A is the same as saying

9^{n} ≡ 1 mod 8

for all n ≥ 1. (It’s also true for n = 0, of course!) C) (Extra Credit-type question) Suppose we used base 9 rather than base 10 to represent

integers. How could you test numbers for divisibility by 8 using the base 9 digits? How could you test numbers for divisibility by 10 using the base 9 digits? Solution: Write integers in base 9:

N = a_{0} + a_{1} · 9 + a_{2} · 9^{2} + ⋯ + a_{k}9^{k},

where the base-9 digits a_{i} ∈ {0, 1, …, 8} for all i ≥ 0. Then the congruence from part B shows that N ≡ S mod 8 where

S = a_{0} + a_{1} + ⋯ + a_{k}

is the sum of the base-9 digits. Hence

N ≡ 0 mod 8 ⇔ S ≡ 0 mod 8.

In words, a number is divisible by 8 if and only if the sum of its base-9 digits is divisible by 8.

Similarly 9 ≡ −1 mod 10, so N written in base 10 is divisible by 10 if the alternating sum of its base-9 digits is zero:

N ≡ 0 mod 10 ⇔ a_{0} − a_{1} + a_{2} + ⋯ + (−1)^{k}a_{k} ≡ 0 mod 10.

V. Show that [x] has a multiplicative inverse in Z/nZ (that is, a [y] such that [x][y] = [1] = [y][x]) if and only if gcd(x, n) = 1.

Solution: If gcd(x, n) = 1, then there are integers y, t such that xy + nt = 1, this shows xy − 1 = (−t)n. Hence, by definition,

xy ≡ 1 mod n,

which implies that [x][y] = [1] in Z/nZ. Conversely, if [x][y] = [1] in Z/nZ, then there is an equation xy − 1 = kn for some integer k. Rearranging this equation gives xy + (−k)n = 1. This implies that 1 ∈ ⟨x, n⟩. But gcd(x, n) is the smallest positive element of ⟨x, n⟩. That implies gcd(x, n) = 1.

VI. A) Find all integer solutions of the congruence 12x ≡ 7 mod 331.

Solution: Since gcd(12, 331) = 1, we can solve this by finding [12]^{−1} in Z/331Z. This is the same sort of computation as in III B above. The answer is [12]^{−1} = [138]. So [x] = [138][7] = [304]. Since the question says find all x ∈ Z that satisfy the congruence, we have the set of solutions 304 + 331Z = {x : x = 304 + 331j, j ∈ Z}.

B) Find all solutions [x] of the equation [17][x] + [4] = [2] in Z/29Z. This is equivalent to the congruence 17x ≡ −2 ≡ 27 mod 29. Since gcd(17, 29) = 1, we have [17]^{−1} exists in Z/29Z. Proceeding as in question III B above, we have [17]^{−1} = [12]. We find [x] = [12][27] = [5]. (If the question said find all x ∈ Z that satisfy the congruence, we would have the set of solutions 5 + 29Z = {x : x = 5 + 29j, j ∈ Z}.)

C) Which [x] ∈ Z/18Z have multiplicative inverses?

Solution: All the [a] with gcd(a, 18) = 1. This gives

(Z/18Z)^{×} = {[1], [5], [7], [11], [13], [17]}.