At the end of the last video, we had one task remaining. We needed to prove this claim:
Claim: For all integers a, b, r, q, k, where b is positive, if a = bq + r and \(k \mid a\) and \(k \mid b\), then \(k \mid r\).
Also remember our definition of "divides":
An integer p divides an integer q (written \(p \mid q\)) if and only if q = pn, for some integer n.
Let's first set up our standard outline for a direct proof: introduce the variables, assume the information in the hypothesis, set out the conclusion as a goal to end the proof.
Proof: Let a, b, r, q, k be integers, with b positive. Suppose that \(a = bq + r\), \(k \mid a\), and \(k \mid b\).
....
Then \(k \mid r\), which is what we needed to show.
Now let's substitute our definition of divides into the statements immediately before and after the gap in the middle.
Proof: Let a, b, r, q, k be integers, with b positive. Suppose that \(a = bq + r\), \(k \mid a\), and \(k \mid b\).
Since \(k \mid a\), \(a = kn\) for some integer n.
Since \(k \mid b\), \(b = km\) for some integer m.
....
So \(r = kt\) where t is an integer.
Then \(k \mid r\), which is what we needed to show.
To fill in the gap, we can take \(a = bq + r\) and solve for r: \( r = a - bq \). Now substitute the values we have for a and b.
\( r = a - bq = kn - (km)q\)
Now peek ahead at the goal at the end of the gap: \(r = kt\). If we want to get the above equation into this form, we need to factor out k. That is:
\( r = a - bq = kn - (km)q = k(n - mq)\)
So t must be \(n - mq\). And t must be an integer because n, m, and q are integers.
Let's get these steps into logical order and use them to fill in the middle of our proof.
Proof: Let a, b, r, q, k be integers, with b positive. Suppose that \(a = bq + r\), \(k \mid a\), and \(k \mid b\).
Since \(k \mid a\), \(a = kn\) for some integer n.
Since \(k \mid b\), \(b = km\) for some integer m.
Since \(a = bq + r\), \( r = a - bq = kn - (km)q = k(n - mq)\).
Let \(t = n - mq\). t must be an integer because n,m,q are integers
So \(r = kt\) where t is an integer.
Then \(k \mid r\), which is what we needed to show.
Now, let's look at our other new definition: congruence mod k. The big idea behind this definition is to treat two two numbers as equivalent if they differ by a multiple of k. So if we set k=5, then
Here is our formal definition:
\(s \equiv t \pmod{k}\) if and only if \( k \mid (s-t) \)
Notice that (mod k) is a modifier on the =. So don't group this in your mind as s = (s mod k).
Sometimes (especially on examlets), we'll ask you to use this equivalent definition, which substitutes in the definition of divides:
\(s \equiv t \pmod{k}\) if and only if s = t + kj, where j is an integer
For understanding what congruence mod k means, it's helpful to know that two equivalent integers have the same remainder mod k:
\(s \equiv t \pmod{k}\) if and only if remainder(s,k) = remainder(t,k)
This isn't a good definition to use in writing proofs, because the definition of remainder is complex (two equations).
Let's do a sample proof using our definition of congruence, and also our defintion of divides. In real life, I'd probably let you avoid some of this complexity by using the alternate definition of congruence. However, I'd like to show you an example of two definitions in succession.
This claim (along with a similar fact for addition) helps establish that congruence interacts nicely with arithmetic.
Claim: For any integers a,b,c,d,k, where k is positive, if \(a \equiv b \pmod{k}\) and \(c \equiv d \pmod{k}\), then \(ac \equiv bd \pmod{k}\).
First, sketch out our standard outline for direct proof:
Proof: let a,b,c,d,k be integers, k positive. Suppose \(a \equiv b \pmod{k}\) and \(c \equiv d \pmod{k}\).
...
So \(ac \equiv bd \pmod{k}\), which is what we needed to prove.
Now, let's apply the definition of congruence to convert the statements about congruence into statements about divides:
Proof: let a,b,c,d,k be integers, k positive. Suppose \(a \equiv b \pmod{k}\) and \(c \equiv d \pmod{k}\).
By the definition of congruence, this means that \(k \mid (a-b)\) and \(k \mid (c-d)\)
...
So \(k \mid (ac-bd) \).
So \(ac \equiv bd \pmod{k}\), which is what we needed to prove.
Now let's apply the definition of divides, to convert the statements before and after the gap into plain algebra:
Proof: let a,b,c,d,k be integers, k positive. Suppose \(a \equiv b \pmod{k}\) and \(c \equiv d \pmod{k}\).
By the definition of congruence, this means that \(k \mid (a-b)\) and \(k \mid (c-d)\)
So \(a-b = km\) and \(c-d = kn\), where m and n are integers.
...
So \(ac-bd = kt \), where t is an integer.
So \(ac \equiv bd \pmod{k}\), which is what we needed to prove.
At this point, it helps to stop and fiddle around with the algebra on scratch paper. I've found that it helps to isolate a, c, and ac on the lefthand sides of these equations. But there are other ways to fill in the algebra steps.
Proof: let a,b,c,d,k be integers, k positive. Suppose \(a \equiv b \pmod{k}\) and \(c \equiv d \pmod{k}\).
By the definition of congruence, this means that \(k \mid (a-b)\) and \(k \mid (c-d)\)
So \(a-b = km\) and \(c-d = kn\), where m and n are integers.
Then \(a = km + b\) and \(c = kn + d \).
...
So \(ac = kt + bd\), where t is an integer.
So \(ac-bd = kt \), where t is an integer.
So \(ac \equiv bd \pmod{k}\), which is what we needed to prove.
Notice that the goal at the end of the gap is a statement with ac on its lefthand side. So let's work out what ac is, using the information above the gap.
Proof: let a,b,c,d,k be integers, k positive. Suppose \(a \equiv b \pmod{k}\) and \(c \equiv d \pmod{k}\).
By the definition of congruence, this means that \(k \mid (a-b)\) and \(k \mid (c-d)\)
So \(a-b = km\) and \(c-d = kn\), where m and n are integers.
Then \(a = km + b\) and \(c = kn + d \).
Multiplying the two equations gives us \(ac = (km + b)(kn + d) \).
...
So \(ac = kt + bd\), where t is an integer.
So \(ac-bd = kt \), where t is an integer.
So \(ac \equiv bd \pmod{k}\), which is what we needed to prove.
Now let's play "compare and contrast" with the top and bottom of the gap. The statement at the end of the gap has only one term involving k. So let's factor k out of the expression at the top of the gap. This is something you probably wouldn't consider doing if you didn't peek ahead at the end of the proof.
Proof: let a,b,c,d,k be integers, k positive. Suppose \(a \equiv b \pmod{k}\) and \(c \equiv d \pmod{k}\).
By the definition of congruence, this means that \(k \mid (a-b)\) and \(k \mid (c-d)\)
So \(a-b = km\) and \(c-d = kn\), where m and n are integers.
Then \(a = km + b\) and \(c = kn + d \).
Multiplying the two equations gives us \(ac = (km + b)(kn + d) = k^2mn + kmd + knb + bd = k(kmn + md + nb) + bd\).
...
So \(ac = kt + bd\), where t is an integer.
So \(ac-bd = kt \), where t is an integer.
So \(ac \equiv bd \pmod{k}\), which is what we needed to prove.
The gap is now mostly cosmetic, so let's fill in the missing bits:
Proof: let a,b,c,d,k be integers, k positive. Suppose \(a \equiv b \pmod{k}\) and \(c \equiv d \pmod{k}\).
By the definition of congruence, this means that \(k \mid (a-b)\) and \(k \mid (c-d)\)
So \(a-b = km\) and \(c-d = kn\), where m and n are integers.
Then \(a = km + b\) and \(c = kn + d \).
Multiplying the two equations gives us \(ac = (km + b)(kn + d) = k^2mn + kmd + knb + bd = k(kmn + md + nb) + bd\).
Let \(t = kmn + md + nb\). t is an integer because k, m, n, b, and d are integers.
So \(ac = kt + bd\), where t is an integer.
So \(ac-bd = kt \), where t is an integer.
So \(ac \equiv bd \pmod{k}\), which is what we needed to prove.
If we had time to rewrite the proof, we could simplify the end by removing the temporary variable t. It could just use \(kmn + md + nb\) directly, mentioning that it must be an integer. That sort of smoothing is optional. On an exam, it wouldn't be worth the time and the risk of introducing mistakes during the rewrite.