ABSTRACT ALGEBRA: OnLine Study Guide, §1.3

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

§ 1.3 Congruences

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), then

a ± 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.

§ 1.3 Solved Problems

In this section, it is important to remember that although working with congruences is almost like working with equations, it is not exactly the same.

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.

Notice that converting to an equation makes it more complicated, because we have to introduce another variable. In the example, we really want a congruence modulo 5, so the next step is to rewrite the equation as

x 7 + 8q (mod 5).

Actually, we can reduce each term modulo 5, so that we finally get

x 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 form

ax b (mod n),

and all simultaneous linear equations of the form

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

Solution

30. Solve the following system of congruences.

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

Solution

31. Solve the following system of congruences.

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

Solution

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¹⁰⁰.

(b) Is 4¹⁰⁰ divisible by 3? Solution

34. Find all integers n for which 13 is a factor of 4(n² + 1). Solution

35. Prove that 10ⁿ⁺¹ + 4 · 10ⁿ + 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