Forward to §1.4 | Back to §1.2 | Up | Table of Contents | About this document

**Definition 1.3.1.**
Let n be a positive integer.
Integers a and b are said to be
**congruent modulo n**
if they have the same remainder when divided by n.
This is denoted by writing
a b (mod n).

**Proposition 1.3.2.**
Let a,b, and n > 0 be integers. Then
a b (mod n)
if and only if n | (a-b).

When working with congruence modulo n, the integer n is called the
**modulus**.
By the preceding proposition,
a b (mod n)
if and only if a-b = nq for some integer q.
We can write this in the form a = b+nq, for some integer q.
This observation gives a very useful method of replacing
a congruence with an equation (over **Z**).
On the other hand, Proposition 1.3.3 shows that
any equation can be converted to a congruence modulo n
by simply changing the = sign to
.
In doing so, any term congruent to 0 can simply be omitted.
Thus the equation a = b+nq would be converted back to
a b (mod n).

**Proposition 1.3.3.**
Let n > 0 be an integer.
Then the following conditions hold for all integers a,b,c,d:

**(a)**If a c (mod n) and b d (mod n), thena ± b c ± d (mod n), and ab cd (mod n).

**(b)**If a+c a+d (mod n), then c d (mod n).If ac ad (mod n) and (a,n)=1, then c d (mod n).

**Proposition 1.3.4.**
Let a and n > 1 be integers.
There exists an integer b such that
ab 1 (mod n)
if and only if (a,n) = 1.

**Theorem 1.3.5.**
The congruence ax b (mod n)
has a solution if and only if b is divisible by d, where d = (a,n).

If d | b, then there are d distinct solutions modulo n,
and these solutions are congruent modulo n / d.

**Theorem 1.3.6. [Chinese Remainder Theorem]**
Let n and m be positive integers, with (n,m)=1.
Then the system of congruences

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

has a solution. Moreover, any two solutions are congruent modulo mn.

What things are the same? You can add or subtract the same integer on both sides of a congruence, and you can multiply both sides of a congruence by the same integer. You can use substitution, and you can use the transitive property:

if a b (mod n) and b c (mod n) then a c (mod n).

You should also review Proposition 1.3.3 and the comments in the text both before and after the proof of the proposition.What things are different? In an ordinary equation you can divide through by a nonzero number. In a congruence modulo n, you can only divide through by an integer that is relatively prime to n. This is usually expressed by saying that

if gcd (a,n) = 1 and ac ad (mod n) then c d (mod n).

Just be very careful!One of the important techniques to understand is how to switch between congruences and ordinary equations. First, any equation involving integers can be converted into a congruence by just reducing modulo n. This works because if two integers are equal, then are certainly congruent modulo n.

The do the opposite conversion you must be more careful. If two integers are congruent modulo n, that doesn't make them equal, but only guarantees that dividing by n produces the same remainder in each case. In other words, the integers may differ by some multiple of n.

The conversion process is illustrated in Example 1.3.5 of the text, where the congruence

x 7 (mod 8)

is converted into the equation
x = 7 + 8q,
for some q in **Z**.

x 7 + 8q (mod 5).

Actually, we can reduce each term modulo 5, so that we finally getx 2 + 3q (mod 5).

You should read the proofs of Theorem 1.3.5 and Theorem 1.3.6 very carefully. These proofs actually show you the necessary techniques to solve all linear congruences of the formax b (mod n),

and all simultaneous linear equations of the formx a (mod n) and x b (mod n),

where the moduli n and m are relatively prime. Many of the theorems in the text should be thought of as ``shortcuts'', and you can't afford to skip over their proofs, because you might miss important algorithms or computational techniques.
**26.**
Solve the congruence
42x 12 (mod 90).
*Solution*

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

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

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

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

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

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

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

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

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

x 5 (mod 25) x 23 (mod 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*

**33.**
(a) Compute the last digit
in the decimal expansion of 4^{100}.

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

**34.**
Find all integers n for which 13 is a factor of 4(n^{2} + 1).
*Solution*

**35.**
Prove that 10^{n+1} + 4 · 10^{n} + 4 is divisible by 9,
for all positive integers n.
*Solution*

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

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