- Definition
- Basics
- Residue Classes
- Casting Out the Moduls (Reducing modulo m)
- Arithmetic
- Division (Cancellation)
- Same 'mod' for Factors
- Factors and Product Theorem
- Multiplicative Inverse

a≡b (mod m) is read as "a is congruent to b mod m".

In a simple, but not wholly correct way, we can think of a≡b (mod m) to mean "a is the remainder when b is divided by m".

For instance, 2≡12 (mod 10) means that 2 is the remainder when 12 is divided by 10.

More formally, we can define:

a≡b (mod m) ⇔m|(a-b), where | means "evenly divides". [1.1]

That is, a≡b (mod m) implies that m divides (a−b).

So, if 5≡22 (mod 17), then 17|(22-5), as it does (it is 1)

We can also define a≡b (mod m) as:

a≡b (mod m) ≡ a=b+km [1.2]

where k is some integer.

So, if 5≡22 (mod 17), then 5=22+17k, where, here, k=−1

We sometimes have a preference for k to be a positive or negative integer such that a is the least positive value satisfying b+km.

This is evident because by definition 1.2:

a≡b (mod m) is defined as a=b+km[1.2, repeated]

a≡a (mod m)↔ m | a−a, because a−a=0, and all numbers divide zero.■

a≡b (mod m), and c≡d (mod m)↔a+c≡b+d (mod m) [3.0]

So, if 5≡15 (mod 10), and 7≡27 (mod 10), then 5+7≡15+27 (mod 10). Both are, in their simplest form, 2 (mod 10).

We can prove [3.0] by using definition [1.2]

a≡b (mod m) is defined as a=b+km[1.2, repeated],

to rewrite 3.0 above as:

a=b+k

c=d+k

where k

Adding 3.1 and 3.2:

a+c=b+d+m(k

which is by definition 1.2:

a+c≡b+d (mod m) ■

If

a≡b (mod m), and c≡d (mod m) by the definition:

a≡b (mod m) is defined as a=b+km[1.2, repeated yet again]

we have

a=b+k

c=d+k

Multiplying these:

a•c=b•d+k

which gives us, by definition:

a•c≡b•d (mod m) ■

We can write a≡b (mod m) using the definition:

a=b+km

If we multiply throughout by -1, we have:

−a=−b−km

taking modulo m (and casting out the m's):

−a≡−b (mod m)

Therefore, we can multiply throughout by −1

a≡b (mod m)↔b≡a (mod m)

a≡b (mod m) is, by definition:

a=b+km

This implies, by forming an expression for b:

b=a−km

which from the definition, we have

b≡a (mod m) ■

{0, 1, 2, ... m−1} [5.1]

we refer to 5.1 as Z

5.1, that is Z

[x]

For instance,

[2]

That is, the class of all numbers which when divided by 5 leave a residue or remainder of 2, modulo 5. There are 5 such classes, one for each of the numbers in 5.2, below, and each has an infinite number of members. The five classes are [0], [1], [2], [3], and [4]

5.1 above is a complete residue system, which contains the least positive members of the appropriate residue class. For instance, the following is a complete residue system modulo 5, using the least positive values:

{0, 1, 2, 3, 4, 5} [5.2]

The next set is also a complete residue system modulo 5, using the least absolute values modulo 5:

{-2, -1, 0, 1, 2}

Naturally, it is normal to express such sets in a logical fashion as in [5.2], but any representative of the respective residue class could be used:

{-5, 6, 2, 3, 9}

which is a complete residue system modulo 5. Each integer is a representative of the respective residue class modulo 5. For instance:

[0]

Let a≡b (mod m)

Suppose a≡c+qm, where q is an integer. By definition:

c+qm=b+km

Making an expression for c:

c=b+(k−q)m

By re-using the definition, we have:

c≡b (mod m)■

We have cast out the multiples of m (or reduced modulo m).

For instance,

15≡1 (mod 7), which we can write as:

2•7+1≡1 (mod 7)

Casting out the 7's, we have, as expected:

1≡1 (mod 7)

Another way to think of casting out is to note that the residue class [m]

Suppose, for example, we have:

2•x≡8 (mod 3)

We can cast out the 3's, noting 5=2•3+2:

2•x≡2 (mod 3)

So x≡1

We can make tables for modular arithmetic. For instance, addition modulo 5:

+ | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|

0 | 0 | 1 | 2 | 3 | 4 |

1 | 1 | 2 | 3 | 4 | 0 |

2 | 2 | 3 | 4 | 0 | 1 |

3 | 3 | 4 | 0 | 1 | 2 |

4 | 4 | 0 | 1 | 2 | 3 |

And multiplication modulo 5:

x | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|

0 | 0 | 0 | 0 | 0 | 0 |

1 | 0 | 1 | 2 | 3 | 4 |

2 | 0 | 2 | 4 | 1 | 3 |

3 | 0 | 3 | 1 | 4 | 2 |

4 | 0 | 4 | 3 | 2 | 1 |

In solving certain problems, we might make appropriate arithmetic tables.

a•b≡a•c (mod m), where a is not equivalent to zero, mod m. (When a≡0, we cannot divide by a).

We can cancel a only when a and m are relatively prime. Otherwise, the rule is 6.2 below.

If a is relatively prime to m, then

b≡c (mod m) [6.1]

For instance, if 9≡21 (mod 4), then we can divide by 3 to get 3≡7 (mod 4), because 3 and 4 are relatively prime.

a≡c (mod m/d) [6.2]

m/d is, of course, an integer.

For instance,

2≡8 (mod 6), but, dividing by 2 gives 1=4 (mod 6) — which is false.

But if we divide throughout (dividing the 2, the 8 and the modulus6), we get the true equivalence: 1≡4 (mod 3).

Actually, [6.1] and [6.2] are effectively the same, since when d=1, then m/d=m.

Also, if m is prime, then we can divide as normal, as in [6.1], providing the divisor is not equivalent to zero. (This does not add anything to the above, though, because if m is prime, and a is not equivalent to zero, modulo m, then a and m are relatively prime, so [6.1] applies.)

then from the definition:

a=b+km [1.2, repeated], we have

a•b=a•c+k•m

where k is an integer and a is not equal to zero.

Dividing by a:

b=c+k•m/a [6.4]

If a and m are relatively prime, and therefore have no common factors, then a must divide k, and not m.

If a did not divide into k or m or both, then
the equivalence (6.3) would not be true, which contradicts our assumption
that it is true. That is, by the definition:

a≡b (mod m) ⇔ m|(a-b) [1.1, repeated]

Equation 6.3 means:

m|a•(b-c), and

k=a•(b-c)/m, so a divides k

a≡b (mod m) ⇔ m|(a-b) [1.1, repeated]

Equation 6.3 means:

m|a•(b-c), and

k=a•(b-c)/m, so a divides k

In 6.4, k/a is an integer, and so 6.4 is by definition 1.2 (or by casting out the modulus):

b≡c (mod m)

Hence when a and m are relatively prime, we can divide as normal.

If a and m are not relatively prime, and d=gcd(a,m), let a=d•n, so from

b=c+k•m/a [6.4, repeated], we have

b=c+k•m/(d•n)

Because n does not divide m, then it must divide k, so k/n is an integer, let it be k

b=c+k

By definition, 6.5 is:

b≡c (mod m/d)

Therefore when a and m are not relatively prime, then when we cancel a, we must also divide the modulus, m, by d=gcd(a,m). ■

When m is a prime number, then the same rules apply, and if a and m are relatively prime, we can divide and cancel as normal. However, we must be careful not to divide by the equivalent of zero. If a and m are not relatively prime when m is prime, then a must be a multiple of m, which is zero modulo m, so we cannot cancel or divide at all. Actually, m being prime or not does not add anything to the above.

That is if a is congruent b modulo mn, then a is also congruent to b modulo m, and to b modulo n.

For example, -10≡32 (mod 42), so -10≡32 (mod 6) and -10≡32 (mod 7)

Also, 22≡7 (mod 15), so 22≡7 (mod 3) and 22≡7 (mod 5). Of course, they don't have the same values!

a=b+k•m•n [7.1]

Let k•m=k

a=b+k

which by definition [1.2], or by casting out the n's is:

a≡b (mod n)

Similarly, let k•n=k

a=b+k

which by definition [1.2], or by casting out the m's is:

a≡b (mod m)

Therefore

a≡b (mod mn)⇔a≡b (mod m), and a≡b (mod n) ■

a≡b (mod m)↔a•n≡b•n (mod mn)

From definition 1.2, we can rewrite the above as:

a=b+km

Multiplying by n, an integer:

n•a=b•n+k•n•m [7.1]

Reapplying definition 1.2, (or casting out the m•n's):

na≡bn (mod mn) [7.2] ■

Also, na≡bn (mod m) [7.3]

by taking [7.1] mod m

So we can multiply a congruence by a number, either multiplying the modul too, or not, as we please.

2≡N (mod 5) [7.4]

6≡N (mod 7) [7.5]

We can make the two moduls the same (mod 35) using the above Factors and Products theorem.

Multiplying [7.4] by 7, the modulus of [7.5], and multiplying [7.5] by 5, the modulus of [7.4]:

14≡7N (mod 35) [7.6]

30≡5N (mod 35) [7.7]

Now they are the same modulus, we can subtract [7.7] from [7.6]:

-16≡2N (mod 35) [7.8]

Dividing by 2 (as 2 is relatively prime to 35):

-8≡N (mod 35)

Choosing the least positive value from the residue class for 35 (or using [1.2]), we have N=-8+35=27.

Therefore 27 is the smallest positive value, which leaves 2 when divided by 5 and leaves 6 when divided by 7. ■

r=1/s, and we say that r is the multiplicative inverse of s. (or, equally, s is the multiplicative inverse of r)

In modular arithmetic, we do much the same, subject to limitations on division. So, if:

a·b≡1 (mod m)

where a, b and m are integers, then b is the multiplicative inverse of a.

However, in modular arithmetic, b may or may not exist.

If a and m are relatively prime, then the inverse, b, exists, and is unique. See division relatively prime.

Otherwise there is no solution.

there is no solution, because gcd(4,6)=2, which does not divide 1. So 4 does not have a multiplicative inverse modulo 6.

■

4·x≡1 (mod 7)

there is a solution because 4⊥7. The solution, by testing is x≡2 (mod 7)

Alternatively, using the definition, we have:

4x=1+7k

If we let k=1, we have

4x=8, or x=2.

Either way we find the multiplicative inverse is 2■

4·x≡1 (mod 51)

There is a solution because 4⊥51. The solution by testing is x≡13 (mod 51) ■

Number Theory Contents

Ken Ward's Mathematics Pages

No script follows:

Ken's book is packed with examples and explanations that enable you to discover more than 150 techniques to speed up your arithmetic and increase your understanding of numbers. Paperback and Kindle: