## § 1.3 Congruences: solved problems

26. Solve the congruence 42x 12 (mod 90).

Solution: We have gcd(42,90) = 6, so by Theorem 1.3.5 there is a solution since 6 is a factor of 12.
Solving the congruence
42x 12 (mod 90) is equivalent to solving the equation
42x = 12 + 90q for integers x and q. This reduces to
7x = 2 + 15q,   or   7x 2 (mod 15).

Equivalently, we obtain
7x 2 (mod 15) by dividing
42x 12 (mod 90) through by 6.

We next use trial and error to look for the multiplicative inverse of 7 modulo 15. The numbers congruent to 1 modulo 15 are 16, 31, 46, 61, etc., and -14, -29, -34, etc. Among these, we see that -14 is a multiple of 7, so we can multiply both sides of the congruence
7x 2 (mod 15) by -2 since
(-2)(7) = -14 1 (mod 15). Thus we have

7x 2 (mod 15)
-14x -4 (mod 15)
x 11 (mod 15).

The solution to the original congruence is
x 11,26,41,56,71,86 (mod 90).

```

```
27. (a) Find all solutions to the congruence 55x 35 (mod 75).

Solution: We have gcd(55,75) = 5, which is a divisor of 35. Thus we have

55x 35 (mod 75)
11x 7 (mod 15)
44x 28 (mod 15)
-x 13 (mod 15)
x 2 (mod 15).

The solution is x 2,17,32,47,62 (mod 75).

(b) Find all solutions to the congruence 55x 36 (mod 75).

Solution: Theorem 1.3.5 implies that there is no solution, since gcd(55,75) = 5 is not a divisor of 36.

```

```
28. (a) Find one particular integer solution to the equation 110x + 75y = 45.

Solution: By Theorem 1.1.6 any linear combination of 110 and 75 is a multiple of the greatest common divisor of the two integers. The matrix form of the Euclidean algorithm produces the following matrices.

Thus (-2)(110) + (3)(75) = 5, and multiplying by 9 yields a solution x = -18, y = 27.

Comment: The matrix computation shows that (110)(15) + (75)(-22) = 0, so adding any multiple of the vector (15,-22) to the particular solution (-18,27) will also determine a solution.

Second Solution: The equation reduces to the congruence
35x 45 (mod 75). This reduces to
7x 9 (mod 15), and multiplying both sides by -2 gives
x -3 (mod 15). Thus 75y = 45 + (3)(110) = 375 and so
x = -3, y = 5 is a solution.

(b) Show that if x = m; y = n is an integer solution to the equation in part (a), then so is
x = m + 15q; y = n -22q, for any integer q.

Solution: If 110m + 75n = 45, then
110(m+15q) + 75(n-22q) = 45 + 110(15)q + 75(-22)q = 45,
since 110(15) - 75(22) = 0.

```

```
29. Solve the following system of congruences.

x 2 (mod 9)       x 4 (mod 10)

Solution: Convert the second congruence to the equation
x = 4 + 10q for some q in Z. Then substituting into the first congruence gives
4 + 10q 2 (mod 9), which reduces to
q 7 (mod 9). Thus the solution is
x = 4 + 10(7) 74 (mod 90).

```

```
30. Solve the following system of congruences.

5x 14 (mod 17)       3x 2 (mod 13)

Solution: This is not the usual form for a system of congruences, since x has a coefficient different from 1. The first step is to reduce the system to the standard form. By trial and error,
7 · 5 1 (mod 17) and so we get

5x 14 (mod 17);
35x 98 (mod 17);
x 13 (mod 17) .

Similarly, 9 · 3 1 (mod 13), and so

3x 2 (mod 13);
27x 18 (mod 13);
x 5 (mod 13).

Having reduced the system to the standard form

x 13 (mod 17)       x 5 (mod 13)

we can solve it in the usual way. From the first equation we have x = 13 + 17q for some q in Z, and then substituting in the second equation leads to a solution.

13+17q 5 (mod 13)
4q 5 (mod 13)
40q 50 (mod 13)
q 11 (mod 13).

x 13 + 17 · 11 200 (mod 221).

```

```
31. Solve the following system of congruences.

x 5 (mod 25)       x 23 (mod 32)

Solution: Write x = 23 + 32q for some q in Z, and substitute to get
23 + 32q 5 (mod 25), which reduces to
7q 7 (mod 25), so q 1 (mod 15).
This gives x 55 (mod 25 · 32).

```

```
32. Give integers a,b,m,n to provide an example of a system of congruences

x a (mod m)       x b (mod n)

that has no solution.

Solution: In the example the integers m and n cannot be relatively prime. This is the clue to take
m = n = 2, with a = 1 and b = 0.

```

```
33. (a) Compute the last digit in the decimal expansion of 4100.

Solution: The last digit is the remainder when divided by 10. Thus we must compute the congruence class of
4100 (mod 10). We have
42 6 (mod 10), and then
62 6 (mod 10). Thus
4100 = (42)50 650 6 (mod 10).

(b) Is 4100 divisible by 3?

Solution: No, since 4100 1100 1 (mod 3).

You could also use the prime factorization 4100 = 2200, and then gcd (3,2200) = 1.

```

```
34. Find all integers n for which 13 | 4(n2 + 1).

Solution: This is equivalent to solving the congruence
4 (n2 + 1) 0 (mod 13). Since gcd (4,13) = 1, we can cancel 4, to get
n2 -1 (mod 13). Just computing the squares modulo 13 gives us

(± 1)2 = 1,
(± 2)2 = 4,
(± 3)2 = 9,
(± 4)2 3 (mod 13),
(± 5)2 -1 (mod 13), and
(± 6)2 -3 (mod 13).

We have done the computation for representatives of each congruence class, so the answer to the original question is
x ± 5 (mod 13).

```

```
35. Prove that 10n+1 + 4 · 10n + 4 is divisible by 9, for all positive integers n.

Solution: This could be proved by induction, but a more elegant proof can be given by simply observing that
10n+1 + 4 · 10n + 4 0 (mod 9) since 10 1 (mod 9).

```

```
36. Prove that the fourth power of an integer can only have 0, 1, 5, or 6 as its units digit.

Solution: Since the question deals with the units digit of n4, it is really asking to find n4 (mod 10). All we need to do is to compute the fourth power of each congruence class modulo 10:

04 = 0,
(± 1)4 = 1,
(± 2)4 = 16 6 (mod 10),
(± 3)4 = 81 1 (mod 10),
(± 4)4 62 6 (mod 10), and
54 52 5 (mod 10).

This shows that the only possible units digits for n4 are 0, 1, 5, and 6.

```

```
Forward to §1.4 | Forward to §1.4 problems | Back to §1.2 problems | Up | Table of Contents