  # Ken Ward's Mathematics Pages

## Number Theory Modular Arithmetic (Congruences)

Number Theory Contents

## Definition

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.

## Basics

### Identity

a≡a (mod m)
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.

We can add (and therefore subtract) congruences, so:
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+k1m [3.1]
c=d+k2m [3.2]
where k1 and k2 are integers.

a+c=b+d+m(k1+k2)
which is by definition 1.2:
a+c≡b+d (mod m)

### Multiplication

We can multiply congruences (and therefore also divide, but with restrictions).
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+k1m [4.1]
c=d+k2m [4.2]
Multiplying these:
a•c=b•d+k2•m•d+k1•k2•m2+k2•m•b
which gives us, by definition:
a•c≡b•d (mod m)

### Multiplying Throughout By Minus 1

We can multiply throughout by −1.
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

### Equivalence

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

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)

## Residue Classes

The set of possible remainders, when an integer is divided by m are:
{0, 1, 2, ... m−1} [5.1]
we refer to 5.1 as Zm

5.1, that is Zm, is called a complete residue system modulo m, because it contains representatives of all the possible remainders when any integer is divided by m. In [5.1], we could call the numbers least positive values of the respective residue class.

[x]m is a residue class modulo m, representing all the numbers which give a remainder x when divided by m. There are m such classes, one for each number in [5.1] above.

For instance,
5={... -13, -8, -3, 2, 7, 12 ...}
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 , , , , and 

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:
5={... -10, -5, 0, 5, 10, 15, ...}

## Casting Out the Moduls (Reducing modulo m)

We can ignore any multiples of m in congruence equations, because they belong to a residue class, with zero as a member.
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]m={... -2m, -m, 0, m, 2m, 3m, ...}, so any multiple of the modulus m is equivalent to zero.

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

## Arithmetic

The purpose of this section is simply to mention there are various airthmetic tables, and gives an example for mulo 5.
We can make tables for modular arithmetic. For instance, addition modulo 5:
 + 0 1 2 3 0 4 0 1 2 3 4 1 2 3 4 0 2 3 4 0 1 3 4 0 1 2 4 4 0 1 2 3

And multiplication modulo 5:
 x 0 1 2 3 0 4 0 0 0 0 0 0 1 2 3 4 0 2 4 1 3 0 3 1 4 2 4 0 4 3 2 1

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

## Division (Cancellation)

### Division Relatively Prime

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

### Division when there is a common divisor

Otherwise, if d=gcd(a,m), then
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.)

#### Proof

If a•b≡a•c (mod m) [6.3]
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

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

b=c+k2•m/d [6.5]
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.

## Same 'mod' for Factors

a≡b (mod mn)↔a≡b (mod m), and a≡b (mod n)
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!

### Proof

a≡b (mod mn) is, by definition:
a=b+k•m•n [7.1]

Let k•m=k2, so [7.1] becomes:
a=b+k2•n,
which by definition [1.2], or by casting out the n's is:
a≡b (mod n)

Similarly, let k•n=k1, so [7.1] becomes:
a=b+k1•m,
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)

## Factors and Product Theorem

This is the converse of the previous section.
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.

#### Example

Suppose a number, say N, when divided by 5 leaves a remainder 2, and when divided by 7 leaves a remainder 6. We seek the value of this number, N. We have the congruences:
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.

## Multiplicative Inverse

If rs=1, where r and s are real numbers, then
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.

#### Examples

4·x≡1 (mod 6),
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

# Faster Arithmetic - by Ken Ward

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: 