Mathematics 243 – Algebraic Structures Selected Solutions – Problem Set 7 October 30, 2006

2.5/35. We let d = gcd(a, n), where n > 1. If there is a solution x ∈ Z of the congruence ax ≡ b mod n, then by the definition of the congruence mod n relation, n|(ax − b), or

\begin{aligned}ax − b & = nq \\ ⇒ b & = −nq + ax \end{aligned}

for some integer q. Because d = gcd(a, n), we have d|a and d|n, so a = sd and n = td for some integers s, t. If we substitute these into the equation for b in the last centered equation above, we get

b = −(td)q + (sd)x = d(−tq + sx),

which shows that d|b. This is what we wanted to show.

2.5/36. Consider a congruence ax ≡ b mod n where gcd(a, n) = d > 1. Also assume d|b so the necessary condition for solutions from problem 35 is satisfied. Write

(1)  a = da_{0} n = dn_{0} and b = db_{0}.

a) We want to show that if x is an integer then

ax ≡ b mod n ⇔ a_{0}x ≡ b_{0} mod n_{0}.

To show this, we will show the two implications separately.

⇒: Assume ax ≡ b mod n. Then ax − b = nq for some integer q. Substitute for a, b, n from (1) above: da_{0}x − db_{0} = dn_{0}q. Since both terms on the left have a factor of d, we can factor it out and cancel to get a_{0}x − b_{0} = n_{0}q, which shows n_{0}|(a_{0}x − b_{0}), so a_{0}x ≡ b_{0} mod n_{0}.

⇐: Now assume a_{0}x ≡ b_{0} mod n_{0}, so n_{0}|(a_{0}x − b_{0}). This says a_{0}x − b_{0} = n_{0}q for some integer q. If we multiply both sides of this equation by d, we get da_{0}x − db_{0} = dn_{0}q. But da_{0} = a, db_{0} = b and dn_{0} = n by (1). So ax − b = nq, which says n|(ax − b) so ax ≡ b mod n.

b) The key observation necessary for this part is that since d = gcd(a, n), when we factor out d, gcd(a_{0}, n_{0}) = 1. This implies that if a_{0}x_{1} ≡ b_{0} mod n_{0} and a_{0}x_{2} ≡ b_{0} mod n_{0}, then a_{0}(x_{1} −x_{2}) ≡ 0 mod n_{0} (substitution rule). This implies n_{0}|a_{0}(x_{1} −x_{2}). But gcd(a_{0}, n_{0}) = 1 so no factor > 1 of n_{0} can divide a_{0}. It follows that n_{0} divides x_{1} − x_{2}, and hence x_{1} ≡ x_{2} mod n_{0}.

Comment: It’s good to be aware that textbook authors often write problems like this so that you can use previous parts to deduce later parts in fairly simple ways. Part c here is a perfect example. c) We are given that a_{0}x_{1} ≡ b_{0} mod n_{0}. Since in_{0} ≡ 0 mod n_{0} for all i = 0, 1, …, d − 1, we have by the substitution rule

a_{0}(x_{1} + in_{0}) = a_{0}x_{1} + ain_{0} ≡ b_{0} + 0 ≡ b_{0} mod n_{0}.

So all the x = x_{1} + in_{0} for i = 0, 1, …, d − 1 are solutions of a_{0}x ≡ b_{0} mod n_{0}. But then part a of the problem implies that ax ≡ b mod n also(!)

d) Aiming for a contradiction, suppose x_{1} + in_{0} and x_{1} + jn_{0} are different (that is, i ≠ j), but that they are congruent mod n, We can take i to be the larger of the two coefficients of n_{0} just by the way we name things, so we will assume 0 ≤ j < i ≤ d − 1. Then

(x_{1} + in_{0}) − (x_{1} + jn_{0}) = (i − j)n_{0}.

Since i, j ≤ d − 1, 0 < i − j < d − 1. Hence 0 < (i − j)n_{0} < (d − 1)n_{0}. But recall that n = n_{0}d. The integer (d−1)n_{0} is positive, but strictly smaller than n = dn_{0}. So there is no way that n can divide it. This contradicts the assumption that x_{1} +in_{0} ≡ x_{1} +jn_{0} mod n.

e) Finally, we want to show that every solution x of ax ≡ b mod n is congruent mod n to one of the solutions from part c. This is another place where we can use parts a and b to get a very quick and slick proof. Let x_{1} be as in part c, and let x be any other solution. Then from part a, a_{0}x ≡ b_{0} mod n_{0}, and a_{0}x_{1} ≡ b_{0} mod n_{0}. Part b then implies that x ≡ x_{1} mod n_{0}, since mod n_{0} there is just one solution of the congruence a_{0}x ≡ b_{0} mod n_{0}. Hence x = x_{1} + in_{0} for some integer i. The integer i can be taken to lie in the range 0 ≤ i ≤ d − 1 since dn_{0} = n. If i ≡ i′ mod d, then x_{1} + in_{0} ≡ x_{1} + i′n_{0} mod n.

2.5/42. To illustrate the procedure for solving congruences ax ≡ b mod n when gcd(a, n) > 1, consider

(2)  21x ≡ 18 mod 30

here a = 21, n = 30 so d = gcd(21, 30) = 3. Note that b = 18 is also divisible by d = 3. Hence

a_{0} = 7, b_{0} = 6, n_{0} = 10.

By part c of problem 36, we start by solving the congruence 7x ≡ 6 mod 10. There is just one solution mod 10, namely x_{1} = 8. Then 3 solutions of (2) that are not congruent mod 30 are the elements of

{x_{1}, x_{1} + n_{0}, x_{1} + 2n_{0}} = {8, 18, 28}.

It is easy to check that each is a solution of (2).