Mathematics 243, section 3 – Algebraic Structures Problem Set 6 due: October 26, 2012

‘A’ Section

1. Solve each of the following congruences for x ∈ ℤ, with 0 ≤ x < n. Note that in each case it is possible to rewrite the given congruence in the form ax ≡ b (mod n) with gcd(a, n) = 1.

a. 7x ≡ 13 (mod 24)

Solution: Since gcd(7, 24) = 1, there exist integers m, n such that 7m + 24n = 1. Applying the Generalized Euclidean Algorithm, the smallest pair m, n that works here is m = 7 and n = 2. This says that 7 · 7 ≡ 1 (mod 24). So multiplying both sides of the congruence by 7, we get x ≡ 91 ≡ 19 (mod 24). The solution with 0 ≤ x < 24 is x = 19.

b. 14x + 25 ≡ 3 (mod 393)

Solution: The congruence can be rewritten as 14x ≡ −22 (mod 393) ≡ 371 (mod 393) Since gcd(14, 393) = 1, there exist integers m, n such that 14m + 393n = 1. Applying the Generalized Euclidean Algorithm, the smallest pair m, n that works here is m = −28 and n = 1. This says that 14 · −28 ≡ 1 (mod 393). So multiplying both sides of the congruence 14x ≡ −22 (mod 393) by −28, we get x ≡ 616 ≡ 223 (mod 393). The solution with 0 ≤ x < 393 is x = 223.

2. What is the ones digit in 43^{15}? Hint: consider 43^{15} (mod 10) and use Theorem 2.22 in the text, or problem B 4 below.

Solution: We have 43 ≡ 3 (mod 10), and computing using Theorem 2.22 or problem B 4 below we see

43^{2} ≡ 3^{2} ≡ 9 (mod 10)43^{3} ≡ 3^{3} ≡ 7 (mod 10)43^{4} ≡ 3^{4} ≡ 1 (mod 10)

Hence the ones digits of the powers of 43 form a cycle of length 4: 3, 9, 7, 1, 3, 9, 7, 1, · · ·. After 15 terms we will have gone through three full cycles and 3 more terms in the fourth cycle, so

43^{15} ≡ 3^{15} ≡ 3^{15 (mod 4)} (mod 10) ≡ 3^{3} (mod 10) ≡ 7 (mod 10).

3. Find a positive integer x that satisfies the two simultaneous congruences

2x + 1 ≡ 5 (mod 9)
3x + 4 ≡ 8 (mod 10)

Explain your method.

4. Proceeding as in question 1 above (but omitting the calculations which are much simpler), we see that x satisfies the first congruence if 2x ≡ 4 (mod 9). Since 2 · 5 ≡ 1 (mod 9), we have x ≡ 2 (mod 9). This says that x = 2 + 9k for some k ∈ ℤ. Similarly, the second congruence says 3x ≡ 4 (mod 10), and 3 · 7 ≡ 1 (mod 10), so x ≡ 8 (mod 10), so x = 6 + 10ℓ for some ℓ ∈ ℤ. Among the integers x = 2, 11, 20, 29, 38, 47, 56, ⋯, satisfying the first congruence, we see that x = 38 also satisfies the second. Note that any x = 38 + 90m is another solution.

‘B’ Section

1. A least common multiple, or lcm, of two nonzero integers a, b is a positive integer m such that

• a|m and b|m, and

• a|c and b|c imply m|c.

Part a below will show that lcm’s always exist, and part b asks you to derive a method for computing them via prime factorizations.

a. Show that if a, b > 0, and d = gcd(a, b) with a = da_{0} and b = db_{0}, then m = da_{0}b_{0} is a least common multiple of a, b.

Proof: Note that d > 0 by definition. Since a, b > 0, then it is clear that a_{0}, b_{0} > 0 too, so da_{0}b_{0} > 0 is also true. We have m = (da_{0})b_{0} = ab_{0} so a|m. Similarly, by commutativity and associativity of multiplication in ℤ, m = (db_{0})a_{0} = ba_{0}. Hence b|m. Finally, we must show that if a|c and b|c, then (da_{0}b_{0})|c. It will be convenient to state and prove the following special case of what we are trying to prove first:

Lemma 1 Let gcd(a_{0}, b_{0}) = 1 and assume that a_{0}|c and b_{0}|c. Then (a_{0}b_{0})|c.

The proof of the lemma is as follows: Since a_{0}|c and b_{0}|c, we have c = a_{0}q = b_{0}q′ for some integers q, q′. Since gcd(a_{0}, b_{0}) = 1, we have 1 = ℓa_{0} + kb_{0} for some integers ℓ, k. But then multiplying both sides of the last equation by q, we have q = ℓa_{0}q + kb_{0}q, so

q = ℓc + kb_{0}q = ℓb_{0}q′ + kb_{0}q = b_{0}(ℓq′ + kq)

This shows that b_{0}|q. Hence (a_{0}b_{0})|c.//

Now we return to the main statement to be proved. Since d = gcd(a, b), in the factorizations a = da_{0} and b = db_{0}, it must be the case that gcd(a_{0}, b_{0}) = 1 (do you see why?) To apply the lemma, we can argue as follows. If a|c and b|c, then d|c as well, so c = da_{0}q = db_{0}q′ for some integers q, q′. By cancellation, this implies a_{0}q = b_{0}q′ = c′ = c/d. By the lemma, (a_{0}b_{0})|c′. Hence (da_{0}b_{0})|c.

b. Deduce from part a that md = ab.

Proof: This follows immediately since by commutativity and associativity of multiplication, md = (da_{0}b_{0})d = (a_{0}d)(b_{0}d) = ab. c. Describe a method for computing a least common multiple of a, b from their standard

form factorizations as on page 92 of the text.

Proof: Suppose that p_{1}, …, p_{k} are all the primes appearing in the standard form factorizations of a or b or both. Then a = ±p_{1}^{e_{1}} ⋯ p_{k}^{e_{k}} and b = ±p_{1}^{f_{1}} ⋯ p_{k}^{f_{k}} for some exponents e_{i}, f_{i} ≥ 0. The lcm of a, b is the integer with standard form factorization

lcm(a, b) = p_{1}^{M_{1}} ⋯ p_{k}^{M_{k}}

where M_{i} = max(e_{i}, f_{i}) for each 1 ≤ i ≤ k.

2. In this problem, you will derive another result first found by the Pythagorean philosophers in ancient Greece. Let a, b be relatively prime integers.

a. Arguing by contradiction, use the fact that 2 is a prime number and Euclid’s Lemma to show that it is never the case that a^{2} = 2b^{2}.

Proof: By Euclid’s Lemma, since 2|(2b^{2}), we have 2|a, or a = 2q for some integer q. But then 4|a^{2}, so we have an equation 4q^{2} = 2b^{2}. By the cancellation law in ℤ, we can write 2q^{2} = b^{2}. Now we repeat the same argument. Since 2|b^{2}, it must be true that 2|b by Euclid’s Lemma. But then 2|a and 2|b so a, b cannot be relatively prime. This contradiction shows that there is no equation a^{2} = 2b^{2} with a, b ∈ ℤ.

b. Explain why the result of part a shows that \sqrt{2} ∈ ℝ is not a rational number.

Proof: If \sqrt{2} ∈ ℚ, then we would have an equation \sqrt{2} = \frac{a}{b} where a, b ∈ ℤ and b ≠ 0. Moreover, recall that by cancelling common factors between the numerator and denominator, any rational number can be written as a fraction in lowest terms. So we can assume gcd(a, b) = 1. But then squaring both sides and multiplying by b^{2} would give 2b^{2} = a^{2}. This is not possible by part a. Therefore, \sqrt{2} ∉ ℚ.

Comments:

i. Here’s an example of a lowest terms fraction. We have \frac{240}{1600} = \frac{3}{20} in lowest terms,

since 240 = 3 · 80 and 1600 = 20 · 80. ii. A possibly fictional story runs that Hippasus of Metapontum (one of the Pythagore-

ans) was murdered by his colleagues for divulging this terrible secret(!) At the time, only rational numbers were accepted as valid objects for mathematical reasoning.

3. Let b > 1 be an integer. Show that every nonnegative integer n can be written in the form

n = d_{0} + d_{1}b + d_{2}b^{2} + ⋯ + d_{m}b^{m}

where 0 ≤ d_{i} < b for all i. (The resulting expansion is called the base-b expansion of n, and the d_{i} are called the base-b digits of n. The usual choice for us is b = 10, but any other base b > 1 works just as well.) Hints: Let m be the largest non-negative integer such that b^{m} ≤ n, and divide b^{m} into n. If you are clever you can then apply an induction hypothesis to finish the proof.

Proof: We use the method of Proof by Complete Induction (see page 75 in the text). For the base case n = 0, we have 0 = 0 + 0 · b + ⋯, which has the required form. (In other words, all the digits are 0.) Now assume that the statement has been proved for all integers n < k and consider n = k. Since b > 1, the powers b^{ℓ} for ℓ ∈ ℤ^{+} grow without any bound. Hence there will be some ℓ = m such that

b^{m} ≤ k < b^{m+1}.  (1)

Apply the division algorithm to divide k by b^{m}. We get

k = qb^{m} + r

where 0 ≤ r < b^{m}. Moreover, by (1), 1 ≤ q < b, so q = d_{m} will be one of our base b digits. Finally since r < b^{m} ≤ k, we can also apply our induction hypothesis to r, and write r = d_{0} + d_{1}b + ⋯ + d_{m−1}b^{m−1}. Therefore

k = r + qb^{m} = d_{0} + d_{1}b + ⋯ + d_{m−1}b^{m−1} + d_{m}b^{m}

as required. (Note that since r < b^{m}, in its base b expansion, only powers of b up to b^{m} can appear. Moreover,

(b − 1) + (b − 1)b + ⋯ + (b − 1)b^{m−1} = (b − 1)(1 + b + ⋯ + b^{m−1}) = b^{m} − 1

so no number ≥ b^{m} can be written using only powers b^{m−1} and smaller.)

4. Give a direct proof (i.e. one not appealing to Theorem 2.22 in the text) of the following statements: If a ≡ b (mod n) and c ≡ d (mod n), then a + c ≡ b + d (mod n) and ac ≡ bd (mod n).

Proof: The given information is equivalent to saying a = b + kn and c = d + ℓn for some integers k, ℓ. Therefore a + c = b + d + (k + ℓ)n, so (a + c) − (b + d) = (k + ℓ)n. Hence by definition, a + c ≡ b + d (mod n). Similarly

ac = (b + kn)(d + ℓn) = bd + n(bℓ + dk + nkℓ).

This implies ac − bd = n(bℓ + dk + nkℓ). By definition, ac ≡ bd (mod n).

5. Show that if m is any integer, then exactly one of the following statements is true: m^{2} ≡ 0 (mod 8), m^{2} ≡ 1 (mod 8), or m^{2} ≡ 4 (mod 8).

Proof: Every integer m satisfies one of the congruences m ≡ k (mod 8) for k = 0, 1, 2, 3, 4, 5, 6, or 7. By Exercise B 4 above, then, m^{2} ≡ k^{2} (mod 8). If k ≡ 0, 4, then k^{2} ≡ 0 (mod 8). (For instance, if k ≡ 4 (mod 8), then k = 8ℓ + 4 for some integer ℓ. But then

k^{2} = 64ℓ^{2} + 64ℓ + 16 = 8(8ℓ^{2} + 8ℓ + 2) ≡ 0 (mod 8).0

Similarly, if k ≡ 1, 3, 5, 7, then k^{2} ≡ 1 (mod 8). Finally, if k ≡ 2, 6, then k^{2} ≡ 4 (mod 8).