*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).

Next problem | Next solution | Up | Table of Contents

*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.

Next problem | Next solution | Up | Table of Contents

*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.

Next problem | Next solution | Up | Table of Contents

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).

Next problem | Next solution | Up | Table of Contents

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
13+17q 5 (mod 13)

4q 5 (mod 13)

40q 50 (mod 13)

q 11 (mod 13).

This leads to the answer,

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

Next problem | Next solution | Up | Table of Contents

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).

Next problem | Next solution | Up | Table of Contents

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.

Next problem | Next solution | Up | Table of Contents

*Solution:*
The last digit is the remainder when divided by 10.
Thus we must compute the congruence class of

4^{100} (mod 10).
We have

4^{2} 6 (mod 10),
and then

6^{2} 6 (mod 10).
Thus

4^{100} = (4^{2})^{50}
6^{50}
6 (mod 10).

(b) Is 4^{100} divisible by 3?

*Solution:*
No, since 4^{100}
1^{100}
1 (mod 3).

You could also use the prime factorization
4^{100} = 2^{200}, and then
gcd (3,2^{200}) = 1.

Next problem | Next solution | Up | Table of Contents

*Solution:*
This is equivalent to solving the congruence

4 (n^{2} + 1) 0 (mod 13).
Since gcd (4,13) = 1, we can cancel 4, to get

n^{2} -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).

Next problem | Next solution | Up | Table of Contents

*Solution:*
This could be proved by induction,
but a more elegant proof can be given by simply observing that

10^{n+1} + 4 · 10^{n} + 4
0 (mod 9)
since 10 1 (mod 9).

Next problem | Next solution | Up | Table of Contents

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

0^{4} = 0,

(± 1)^{4} = 1,

(± 2)^{4} = 16 6 (mod 10),

(± 3)^{4} = 81 1 (mod 10),

(± 4)^{4} 6^{2} 6 (mod 10), and

5^{4} 5^{2} 5 (mod 10).

This shows that the only possible units digits for n^{4} are
0, 1, 5, and 6.

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

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