Notes also available as PDF.
What we covered last week:
This week’s topics:
These all are useful when you deal with integral numbers of things
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 r congruence 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 c modulo 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:


This works as you expect. Addition is commutative and associative. There is an additive identity, 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 multiplicative
inverse. Some residues have inverses, and some don’t:


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 straightforward 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:
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,
\mathop{lcm}\nolimits (a,b) = {2}^{3} ⋅ {3}^{3} ⋅ {5}^{2} ⋅ {7}^{1} = 37\kern 1.66702pt 800.

And for more than two integers, take the maximum across all the exponents of corresponding factors.
Another relation for two integers a and b is that
\mathop{lcm}\nolimits (a,b) = {ab\over
d} .

So given a = 1350, b = 1400, and d = 50,
\mathop{lcm}\nolimits (1350,1400) = {1350 ⋅ 1400\over
50} = {1\kern 1.66702pt 890\kern 1.66702pt 000\over
50} = 37\kern 1.66702pt 800.

This does not hold directly for more than two integers.
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 nonnegative. And because (a,b) = (b,a), we can assume b ≥ a.
Let d = (a,b). Last week we showed that if da and db, then dra + sb for any integers r and s. Then because da and db, we have db  qa or dr. 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 dr' 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.
Consider calculating (53,77). Following the steps, we have
And thus (53,77) = 1.
For another example, take (128,308). Then
So (128,308) = 4.
Later in the semester, we will examine linear equations ax + by = c over real numbers. But many everyday 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.
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 no integer 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}_{k1}. Working backward one step,
So d = {r}_{k1} = i ⋅ {r}_{k3} + j ⋅ {r}_{k4} where i and j are integers. Continuing, the gcd d can be expressed as an integer combination of each pair of remainders.
Returning to the example of (77,53),
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
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:
Substituting back,
So we can generate any solution to 12x + 25y = 331 with the equations
Using these, we can find a “smaller” solution. Try making x nonnegative with
Substituting t = 27,
x = 13,\quad \text{and}\quad y = 7.

Interestingly enough, this must be the only nonnegative solution. A larger t will force y negative, and a smaller t forces x negative. But the solution for t = 26 is still “small”,
x = 12,\quad \text{and}\quad y = 19.

Practice is absolutely critical in this class.
Groups are fine, turn in your own work. Homework is due in or before class on Mondays.
Note that you may email homework. However, I don’t use Microsoft^{TM} products (e.g. Word), and software packages are notoriously finicky about translating mathematics.
If you’re typing it (which I advise just for practice in whatever tools you use), you likely want to turn in a printout. If you do want to email your submission, please produce a PDF or PostScript document.