Algebra 1 Assignment 3 Solutions

Problem 1 The simplest way to do this is to check all the cases, but to do less work we make the following observation: ax ≡ b mod (n) and ay ≡ b mod (n) ⇔ a(x − y) ≡ 0 mod (b) (check it!). So if x is a solution of ax ≡ b mod (n) then the other solutions of the equation are of the form x + a′ where n | aa′. We have,

(a) 3 ∗ 4 ≡ 12 ≡ 5 mod (7) and there are no other solutions because 7 is prime.

(b) 3 ∗ 4 ≡ 12 ≡ 1 mod (11) and x = 4 is the only solution.

(c) 3 ∗ 2 ≡ 6 mod (15) so we have x = 2 is a solution but notice that 15 | 3 ∗ 5 and 15 | 3 ∗ 10 so we have that x = 2 + 5 = 7 is a solution and x = 12 is also a solution (moreover they are the only ones)

(d) We try for x = 0, 1, 2, 3, 4, 5, 6 and notice that none of these work, we can stop, why? We have that 6 ∗ 7 ≡ 6 ∗ 14 ≡ 0 mod (21) so it follows that if y is a solution to our equation, we can chose y < 21 and we also have that y −7, y −14 is a solution, thus if there is a solution 21 > y > 6 then there exists a solution 0 ≤ y′ ≤ 6 but we checked that there were none.

Problem 2 We compute the squares in ℤ_{8}

0^{2} = 0
1^{2} = 1
2^{2} = 4
3^{2} = 9 = 1
4^{2} = 16 = 0
5^{2} = 25 = 1
6^{2} = 36 = 4
7^{2} = 49 = 1

We see that the possible sums of three squares are: 1 + 1 + 1 = 3; 1 + 1 + 4 = 6; 1 + 4 + 4 = 9 = 1; 4 + 4 + 4 = 12 = 4. So seven can not be expressed as a sum of three squares in ℤ_{8}.

Now suppose towards a contradiction that every integer could be expressed as a sum of three squares. Let n ∈ [7]_{8} ⊂ ℤ where [7]_{8} is the equivalence class of integers congruent to 7 mod(8). Then by our supposition n = a^{2} + b^{2} + c^{2} for some a, b, c ∈ ℤ, hence we have the congruence equation a^{2} + b^{2} + c^{2} ≡ n ≡ 7 mod (8). This is a contradiction, it follows that some integers (in particular 7) can not be expressed as a sum of three squares.

Problem 3 Show that a^{5} ≡ a mod (30) for all integers a. We have the following equivalencies

a^{5} ≡ a mod (30)
⇔ a^{5} − a ≡ 0 mod (30)
⇔ 30 | a^{5} − a

We also have that 30 | (a^{5} −a) if and only if 2, 3 and 5 divide a^{5} −a. One side of this implication is clear i.e. if 30 | x then 2, 3 and 5 also divide x. On the other hand suppose that 2, 3 and 5 divide x. Then by the fundamental theorem of arithmetic we have the unique prime factorization x = ±1∗2^{ϵ_{1}} ∗3^{ϵ_{2}∗}5^{ϵ_{3}} ∗… and in particular we find that ϵ_{1}, ϵ_{2}, ϵ_{3} are all at least 1. So 30 = 2∗3∗5 divides x as well. (It is sometimes useful to think that a divides b if and only if b “contains” a’s prime factorization.)

So if we show that n | a^{5} − a for all a when n = 2, 3, 5, we’re done. So we check for each of them. I’ll only do the case for n = 5, we need to check for a = 0, 1, 2, 3, 4. When a = 0, 1 the equation clearly holds. For the rest:

4^{5} = 4^{2} ∗ 4^{2} ∗ 4 ≡ 1 ∗ 1 ∗ 4 ≡ 4 mod (5)
3^{5} = 3^{2} ∗ 3^{2} ∗ 3 ≡ (−1) ∗ (−1) ∗ 3 ≡ 3 mod (5)
2^{5} = 4 ∗ 2^{3} ≡ (−1) ∗ 3 ≡ 2 mod (5)

So we have that for each a ∈ ℤ, a^{5} ≡ a mod (5). Similarly the equations also hold for all a modulo 2 and 3. We can therefore infer that for all a ∈ ℤ, a^{5} ≡ a mod (30).

Problem 4 We first consider ℤ_{11}. We start checki and find that in ℤ_{11}:

2 = 2 2^{2} = 4 2^{3} = 8 2^{4} = 16 = 5 2^{5} = 2 ∗ 5 = 10 2^{6} = 2 ∗ 10 = 9 2^{7} = 2 ∗ 9 = 7 2^{8} = 2 ∗ 7 = 3 2^{9} = 2 ∗ 3 = 6 2^{10} = 2 ∗ 6 = 1

So 2 is a primitive root of ℤ_{11}. And for the record, there is not really a nice way to find such roots.

For ℤ_{24} a totally different approach is in order, checking every elements will do the trick but it is too much work, especially because ℤ_{24} has no such primitive roots. The two next propositions illustrate what’s going on.

Proposition 1: Let R be a commutative ring and suppose that a, b ∈ R are such that a, b ≠ 0 but ab = 0, then a may not have a multiplicative inverse. Proof: Suppose that a ≠ 0 did have a multiplicative inverse a^{−1} but that there was some b ≠ 0 such that ab = 0.

b = 1 ∗ b
= (a^{−1}a)b
= a^{−1}(ab) = a^{−1} ∗ 0 = 0
⇒ b = 0

Which is a contradiction.□

Proposition 2: If ℤ_{n} has a primitive root, then all its non-zero elements have multiplicative inverses.

Proof: Let x ∈ ℤ_{n} be any nonzero element and let a be a primitive root. Then for some l, m ∈ ℕ, x = a^{l} and a^{m} = 1. We may assume that l < m if not then for some k, l ≤ km and we have a^{km} = (a^{m})^{k} = 1^{k} = 1 so we may replace m by km. Let j = m − l ≥ 0 then we have that xa^{j} = a^{l+j} = 1, hence x has a multiplicative inverse. Since x is arbitrary the Proposition is proved. □

Now we have in ℤ_{24} that 2 ∗ 12 = 0 so by Proposition 1, 2 or 12 may not have a multiplicative inverses. It then follows from Proposition 2 that ℤ_{n} has no primitive root.

Problems 5 and 6 If x^{2} ≡ 1 in ℤ_{n} this means in particular that n | (x^{2} − 1) (look at Problem 3 if this isn’t clear) which implies n | (x + 1)(x − 1).

For Problem 5 suppose we can take ℤ_{80}. Notice that 9^{2} = 81 = 1 but that 9 ≠ 1, −1. So we have a counterexample. By the way I picked 80 because 80 = (9 + 1)(9 − 1).

If n > 2 is prime, notice the following: Suppose there was some [x] ∈ ℤ_{n} such that [x]^{2} = [1]. If [x] ≠ [1] or [−1] then [x + 1], [x − 1] ≠ [0]. Picking a representative x_{0} ∈ ℤ from [x] such that x_{0} < n gives us that in ℤ, n | (x_{0} − 1)(x_{0} + 1), and since n is prime it must divide one of the factors on the right, but notice that x_{0} − 1 and x_{0} + 1 are both nonzero and less than n, so n can’t can’t divide them which is a contradiction. We infer that the only possibilities for [x] are [1] and [−1].

Problem 7 Suppose that gcd(a, n) = 1 then there exist p, q ∈ ℤ such that pa + qn = 1. It follows that pa + qn ≡ 1 mod (n) so we can write [pa] + [qn] = [1](⋆) in Z_{n}. But note that the term [qn] = [q][n] = [0][n] = [0]. So in fact (⋆) yields [p][a] = [1] therefore[a] has the multiplicative inverse [p].

On the other hand, suppose that [a] ∈ ℤ_{n} had a multiplicative inverse [a′], then picking a representative a′_{0} ∈ ℤ of the equivalence class [a′] we get the congruence relation aa′_{0} ≡ 1 mod (n). So applying the division algorithm in ℤ we get aa′_{0} = pn + 1 for some p ∈ ℤ which implies aa′_{0} − pn = 1. We know that gcd(a, n) is the smallest strictly positive integer representable as a linear combination of a and n, so it follows that gcd(a, n) = 1.

Problem 8 By Problem 7, the invertible elements in ℤ_{5} correspond to equivalence classes of elements relatively prime to 5, so they are [1], [2], [3], [4]. Similarly for ℤ_{12} the invertible elements are [1], [5], [7], [11] i.e. everything relatively prime to 12.