On this page, a, b, k, and m are always integers.
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.■
Addition
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.
Adding 3.1 and 3.2:
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,
[2]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 [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]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
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.
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)
■
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:
