Remember the divisibility form for b
with respect to dividing by a\mathrel{≠}0,
b = q ⋅ a + r,\text{ with }0 ≤ r < |a|.
This form is unique for a given a
and b.
Consider a = 5. There are only
five possible values of r,
zero through four. Because the form is unique, we can place every
b into
one of rcongruence classes. Each congruence class is a set. For
a = 5, we
have the following classes:
\{\mathop{\mathop{…}},
-10,
-5,
0,
5,
10,
\mathop{\mathop{…}}\}
= \{5k + 0\kern 1.66702pt |\kern 1.66702pt k J\}
\{\mathop{\mathop{…}},
-9,
-4,
1,
6,
11,
\mathop{\mathop{…}}\}
= \{5k + 1\kern 1.66702pt |\kern 1.66702pt k J\}
\{\mathop{\mathop{…}},
-8,
-3,
2,
7,
12,
\mathop{\mathop{…}}\}
= \{5k + 2\kern 1.66702pt |\kern 1.66702pt k J\}
\{\mathop{\mathop{…}},
-7,
-2,
3,
8,
13,
\mathop{\mathop{…}}\}
= \{5k + 3\kern 1.66702pt |\kern 1.66702pt k J\}
\{\mathop{\mathop{…}},
-6,
-1,
4,
9,
14,
\mathop{\mathop{…}}\}
= \{5k + 4\kern 1.66702pt |\kern 1.66702pt k J\}
We say that two numbers are in the same congruence class for a given
a by
b ≡ c\kern 18mu ({\rm mod}\kern 6mu a).
Or b is
equivalent to cmodulo a.
A collection of one entry from each set is called a complete residue system. We
typically select the least positive numbers, those in bold above.
We define arithmetic on congruence classes by arithmetic on the remainders. The
remainders wrap around every multiple of the modulus. For example, addition
modulo 4 and modulo 5 are defined as follows:
+\kern 18mu ({\rm mod}\kern 6mu 4)
0
1
2
3
0
0
1
2
3
1
1
2
3
0
2
2
3
0
1
3
3
0
1
2
+\kern 18mu ({\rm mod}\kern 6mu 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
This works as you expect. Addition is commutative and associative. There is an additiveidentity, because b + 0 ≡ 0\kern 18mu ({\rm mod}\kern 6mu a).
Unlike the positive integers, there also is an additive inverse for every residue because
b + (a - b) ≡ 0\kern 18mu ({\rm mod}\kern 6mu a).
Multiplication likewise is commutative and associative, and there is a
multiplicative identity, 1. The unusual aspect appears with the multiplicativeinverse. Some residues have inverses, and some don’t:
×\kern 18mu ({\rm mod}\kern 6mu 4)
0
1
2
3
0
0
0
0
0
1
0
1
2
3
2
0
2
0
2
3
0
3
2
1
×\kern 18mu ({\rm mod}\kern 6mu 5)
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
The difference here is that 5 is prime while 4 is composite. Any factor of the modulus
will not have a multiplicative inverse.
One common application of modular arithmetic (besides telling time) is in testing
whether one integer divides another. We use modular arithmetic and positional
notation. Both help us break the larger problem, testing divisibility of a potentially
large number, into the smaller problems of breaking apart the number and evaluating
expressions in modular arithmetic.
If a\mathrel{∣}b
(a divides
b), then
b ≡ 0\kern 18mu ({\rm mod}\kern 6mu a). So we can test for
divisibility by expanding b
in positional notation and evaluating the operations modulo
a.
When the divisor is small, a straight-forward evaluation is simplest. Because
10 ≡ 1\kern 18mu ({\rm mod}\kern 6mu 3), we
can test for divisibility by 3 by adding the number’s digits modulo 3. For
example,
Hence 3 ∤ 1234. The same “trick”
applies to 9 because 10 ≡ 1\kern 18mu ({\rm mod}\kern 6mu 9).
When the divisor is closer to a power of 10, using a negative element
of the congruence class may be useful. For 11, remember that 10 and
- 1 are in the same
congruence class because 10 = 0 ⋅ 11 + 10
and - 1 = -1 ⋅ 11 + 10.
So 10 ≡-1\kern 18mu ({\rm mod}\kern 6mu 11)
and we can expand the powers of ten,
Hence 11 ∤ 1234.
Here, the “trick” form is that you start from the units digit and then alternate
subtracting and adding digits.
For more complicated examples, we can factor the divisor. To test if a number is divisible by
72, factor 72 = {2}^{3} ⋅ {3}^{2} = 8 ⋅ 9.
Then test if the number is divisible by 8 and by 9.
If a\mathrel{∣}b and
c\mathrel{∣}b, then it may be
true that ac\mathrel{∣}b. This is
certainly true of a
and b
are powers of different primes. The key point is that
a and
b share no common
divisors. Note that 72 = 6 ⋅ 12,
6\mathrel{∣}24, and
12\mathrel{∣}24, but
obviously 72 ∤ 24
because 24 < 72.
So finding common divisors is useful for testing divisibility. The greatest common
divisor of numerator and denominator reduces a fraction into its simplest form. In
general, common divisors help break problems apart.
Written (a,b)
or \mathop{gcd}(a,b),
the greatest common divisor of a
and b
is the largest integer d ≥ 1
that divides both a
and b.
We’ll discuss a total of two methods for finding the greatest common divisor. The first
uses the prime factorization, and the second uses the divisibility form in the Euclidean
algorithm. Later we’ll extend the Euclidean algorithm to provide integer solutions
x and
y to
equations ax + by = c.
The prime factorization method factors both
a and
b.
Consider a = 1400 = {2}^{3} ⋅ {5}^{2} ⋅ 7
and b = 1350 = 2 ⋅ {3}^{3} ⋅ {5}^{2}.
Lining up the factorizations and remembering that
{x}^{0} = 1, we
have
a = 1400 = {2}^{3}
⋅ {3}^{\mathbf{0}}
⋅ {5}^{\mathbf{2}}
⋅ {7}^{1}, and
b = 1350 = {2}^{\mathbf{1}}
⋅ {3}^{3}
⋅ {5}^{\mathbf{2}}
⋅ {7}^{\mathbf{0}}.
Now chose the least exponent for each factor. Then
d = {2}^{1} ⋅ {3}^{0} ⋅ {5}^{2} ⋅ {7}^{0} = 50
is the greatest common divisor. For more than two integers, factor all the integers
and find the least exponents across the corresponding factors in all of the
factorizations.
For an example use, reduce a fraction a∕b = 1350∕1400
to its simplest form. To do so, divide the top and bottom by
d = 50. Then
a∕b = 1350∕1400 = 27∕28.
Now we can state the requirement about divisibility given some factors:
If two relatively prime integers a
and b
both divide c,
then ab
divides c.
Some other properties of the gcd:
Because the gcd is positive, (a,b) = (|a|,|b|).
(a,b) = (b,a)
If the gcd of two numbers is 1, or (a,b) = 1,
then a
and b
are called relatively prime.
Before the other method for finding the gcd, we consider one related quantity.
The least common multiple, often written \mathop{lcm}\nolimits (a,b),
is the least number L ≥ a
and L ≥ b
such that a\mathrel{∣}L
and b\mathrel{∣}L.
There are clear, every day uses. Think of increasing a recipe when you can only buy
whole bags of some ingredient. You need to find the least common multiple of the
recipe’s requirement and the bag’s quantity. Or when you need to find the next day
two different schedules intersect.
Again, you can work from the prime factorizations
a = 1400 = {2}^{\mathbf{3}}
⋅ {3}^{0}
⋅ {5}^{\mathbf{2}}
⋅ {7}^{\mathbf{1}}, and
b = 1350 = {2}^{1}
⋅ {3}^{\mathbf{3}}
⋅ {5}^{\mathbf{2}}
⋅ {7}^{0}.
Now the least common multiple is the product of the larger exponents,
Another method for computing the gcd of two integers
a and
b is due
to Euclid. This often is called the first algorithm expressed as an abstract sequence of
steps.
We start with the division form of b
in terms of a\mathrel{≠}0,
b = qa + r\text{ with }0 ≤ r < a.
Because (a,b) = (|a|,|b|), we can
assume both a and
b are non-negative.
And because (a,b) = (b,a),
we can assume b ≥ a.
Let d = (a,b). Last week
we showed that if d|a
and d|b, then
d|ra + sb for any
integers r
and s. Then
because d|a
and d|b, we
have d|b - qa or
d|r. So we have that
d = (b,a) also divides
r. Note that any
number that divides a
and r also
divides b,
so d = (a,r).
Continuing, we can express a
in terms of r
as
a = q'r + r'\text{ with }0 ≤ r' < r.
Now d|r' and
d = (r,r'). Note
that r' < r < a,
so the problem keeps getting smaller! Eventually, some remainder will be zero. Then
the previous remainder is the greatest common divisor.
Find {q}_{0}
and {r}_{0}
in b = {q}_{0}a + {r}_{0}
with 0 ≤ {r}_{0} < a.
If {r}_{0} = 0,
then (a,b) = a.
Let {r}_{-1} = a
to make the loop easier to express.
Then for i = 1,\mathop{\mathop{…}}
Find {q}_{i}
and {r}_{i}
in {r}_{i-2} = {q}_{i}{r}_{i-1} + {r}_{i}
with 0 ≤ {r}_{i} < {r}_{i-1}.
If {r}_{i} = 0,
then (a,b) = {r}_{i-1}
and quit.
Otherwise continue to the next i.
Consider calculating (53,77).
Following the steps, we have
Later in the semester, we will examine linear equations
ax + by = c over
real numbers. But many every-day applications require integer solutions.
We can use the Euclidean algorithm to find one integer solution to
ax + by = c or
prove there are none. Then we can use the computed gcd to walk along the line to all
integer solutions.
Say we need to solve ax + by = c
for integers a,
b, and
c to find integer
solutions x
and y.
In general, equations over integers are called Diophantine equations
after Diophantus of Alexandria (approx. 200AD-290AD). He was
the first known to study these equations using algebra. The form
ax + b = c
describes linear Diophantine equations.
Let d = (a,b). Then, as
before, d\mathrel{∣}ax + by for
all integers x
and y. So
d\mathrel{∣}c for any solutions to exist.
If d ∤ c, then there are nointeger solutions. If a
and b are relatively prime,
then (a,b) = 1 and solutions
exist for any integer c.
Consider solving ax + by = d.
Because d\mathrel{∣}c, we can
multiply solutions to ax + by = d
by c∕d to obtain
solutions of ax + by = c.
To solve ax + by = d
we work backwards after using the Euclidean algorithm to compute
d = (a,b).
Say the algorithm required k
steps, so d = {r}_{k-1}.
Working backward one step,
So d = {r}_{k-1} = i ⋅ {r}_{k-3} + j ⋅ {r}_{k-4} where
i and
j are integers.
Continuing, the gcd d
can be expressed as an integer combination of each pair of remainders.
To solve 53x + 77y = 22, we
start with 53 ⋅ 16 + 77 ⋅ (-1) = 1.
Multiplying by 22,
53 ⋅ (16 ⋅ 22) + 77 ⋅ (-1 ⋅ 22) = 22,
and x = 352,
y = -22 is one
solution.
But if there is one solution, there are infinitely many! Remember that
d = (a,b), so
a∕d and
b∕d are integers. Given
one solution x = {x}_{0}
and y = {y}_{0}, try
substituting x = {x}_{0} + t ⋅ (b∕d)
and y = {y}_{0} - t ⋅ (a∕d) for any
integer t.
Then
\eqalignno{
a({x}_{0} + t ⋅ (b∕d)) + b({x}_{0} - t ⋅ (a∕d)) & = a{x}_{0} + b{x}_{0} + t ⋅ (ab∕d)) + -t ⋅ (ba∕d)) & &
\cr
& = a{x}_{0} + b{x}_{0} = c. & &
}
Actually, all integer solutions to ax + by = c
are of the form
x = {x}_{0} + t ⋅ (b∕d),\quad \text{and}\quad y = {y}_{0} - t ⋅ (a∕d),
where t is any
integer, d = (a,b),
and {x}_{0}
and {y}_{0}
are a solution pair.
Another example, consider solving 12x + 25y = 331.
First we apply the Euclidian algorithm to compute
(12,25) = 1:
Interestingly enough, this must be the only non-negative solution. A larger
t will force
y negative, and
a smaller t forces
x negative. But
the solution for t = 26
is still “small”,
J\}