Integers and Congruences - Part IV

Congruences

Why are congruences interesting and important? When we talk about congruences we are talking about 'modulo'. They are important because, for instance, they are used within computing, for example within hash tables and RSA encryption. ISBN:s are based on them. Another area where they are used is in the construction of so called latin squares.

Definition: Congruence modulo n

Let n be an integer. Two integers a and b are congruent modulo n if they have the same principal remainfer when they are divided by n. Write a b (mod n).

Example

17 and -3 are congruent modulo 20 as 17 = 020+17 and -3 = -120+17.

OBS!

Note that an integer is congruent modulo n to exactly one integer k in the range 0 k < n. (Why? Because the principal remainder is unique.)

We can express congruence modulo n in a number of ways. For instance, if a=kn+r and b=ln+r, then a-b=(k-l)n which means that a-b is divisible by n, which can be written as a - b 0 (mod n). If we let k-l=t then a-b=tn so a=b+tn. The next theorem summarises these results.

Theorem: a and b are congruent modulo n

Two integers a and b are congruent modulo n iff

1. a b (mod n),
2. there are integers q₁, q₂, and r such that a=nq₁+r and b=nq₂+r where 0 r < n.
3. there is an integer t such that a=b+tn.
4. a - b 0 (mod n).
5. n | (a-b).
6. a and b have the same principal remainder on division by n.

Now that we know various ways to check if two integers are congruent modulo n, we will look at addition and multiplication of two integers modulo n.

Back to Division

As the definition indicates, when we are dealing with congruences, we are really dealing with 'remainders'. We will prove the next theorem by looking at remainders. It is useful to remember that a result which is true for congruences is also true for remainders.

Theorem: Congruences

Let n be a given positive integer and a,b,c be any integers. Then the following are true.

1. a a (mod n)
   
2. if a b (mod n) then b a (mod n)
   
3. if a b (mod n) and b c (mod n) then a c (mod n)
   
4. if a b (mod n) and c d (mod n), then a+c b+d (mod n) and ac bd (mod n)
   
5. if a b (mod n) then a+c b+c (mod n) and ac bc (mod n)
   
6. if a b (mod n) then a^k b^k (mod n), for positive integers k.

Proof

1. a obviously has the same remainder as a when divided by n. [It may seem rather silly to state this, but it is needed for chapter 4 in Chetwynd and Diggle, as are the next two results.]
2. if a has the same remainder as b then b has the same remainder as a on division by n.
3. Suppose a and b have the same remainder r on division by n. If b and c also have the same remainder, then c has the remainder r on division by n. Hence and a and c have the same remainder and so are congruent modulo n.
4. Suppose a b (mod n) and c d (mod n). Then there are integers k,l,r,s such that a=kn+b and c=ln+d. Now
   a+c=kn+b+ln+d=n(k+l)+(b+d) b+d (mod n).

   Also

   ac=(kn+b)(ln+d)=n(kl+d+b)+(bd) bd (mod n).
5. This follows from (iv) by putting d=c as c c (mod n).
6. Suppose a b (mod n) then a^k b^k (mod n) is true for k=1. Suppose it is true for k=t 1. Then we have a^t b^t (mod n) and a b (mod n), so we can apply (iv) to get a^t+1 b^t+1. Hence the proposition is true for all positive integers , by induction.

Now we have some results, we will start manipulating congruences. We will find the remainder when some integers are multiplied together, then we will look at some division rules - do you know how to check if an integer is divisible by 9 or by 11 or by 4?

Example

Find the remainder when 3865920357 is divided by 8.

Solution

We can find the remainder when an integer is divided by 8, by looking at the integer modulo 8.

38651 (mod 8) and 9203575 (mod 8) so 3865920357 155 (mod 8). Hence the remainder when 3865920357 is divided by 8 is 5.

Example

Find the principal remainder when 8754 = 810³ + 710² + 510 + 4 is divided by 9.

Solution

To find the remainder when an integer is divided by 9, we work modulo 9.

By the theorem on congruences above, (iv) we know that 10^k 1^k 1 (mod 9), as 10 1 (mod 9). By part (v), a10^k a 1 (mod 9), so 810³ 8 (mod 9), 710² 7 (mod 9) and 510 5 (mod 9). By applying (iv), we have

8754 = 810³ + 710² + 510 + 4 8+7+5+4 -1 + 7 +9 6 (mod 9).

Hence the remainder when 8754 is divided by 9 is 6.

Note

If a 0 (mod n), then a is divisible by n. We can use this to check if an integer a is divisible by, for example, 9. Basically, we follow the method in the example above.

Example: Rule to check for divisibility by 9

If a 0 (mod 9), then a is divisible by 9. Let (a_ka_k-1...a₂a₁a₀) ₁₀ be the base 10 representation of a. Then

a	=	(akak-1...a2a1a0) 10
	=	10kak + 10k-1ak-1 + ... + 102a2 + 10a1 + a0
		ak + ak-1 + ... + a2 + a1 + a0 (mod 9) as 10k 1 (mod 9).

Hence 9 | a if and only if 9 | (a_k + a_k-1 + ... + a₂ + a₁ + a₀), that is, the sum of its digits.

Exercises

1. Find the remainder the following integers are divided by 9
   1. 15492
   2. 12304
2. Find the remainder the following integers are divided by 7
   1. 1549227985
   2. 12304279627
   3. 359¹²⁴ [Hint: What is 2⁴ modulo 7? Note that 6 -1 (mod 7).]
3. Find a rule for checking whether an integer is divisible by 11.
4. Find a rule for checking whether an integer is divisible by 8. [Hint: what is 10³ modulo 8?]