This week we talked about how to prove things about numbers that evenly divide other numbers.
3 | 12 says “3 evenly divides 12”. This is equivalent to saying 12 = 3k where k is an integer. This turns out to be useful notation, because it lets you say things like 2 | n -> n is even or 2 ⍀ n -> n is odd. footnote:[My apologies if the ⍀ symbol shows up as a box with numbers inside. Just picture an | with a through it, and you’ll get the idea.] This clearly suggests that there are other classes of numbers that we don’t have convinient names for, like 3 | n and 3 ⍀ n. 3 ⍀ n isn’t really equivalent to odd, however, because it is bigger than 3 | n. Perhaps a better way to look at this could be seen by introducing some new notation.
n = 0 mod 3 footnote:[Pronounced “enn equals zero modulo three”] means n = 3k + 0 where k is an integer. You might notice that this is equivallent to 3 | n, and you would be right. This new syntax also allows us to say n = 1 mod 3 = 3k + 1 or n = 2 mod 3 = 3k + 1. These are equivalent to 3 | (n - 1) and 3 | (n - 2), respectively. This allows us to see that you can use division by 3 to split integers into 3 different classes.
This is true for all natural numbers: you can cut integers into n different pieces by looking at their value mod n. Arithmetic mod n is also very simple. For example, if a = 3 mod 5 and b = 1 mod 5, a + b = 4 mod 5. If c = 4 mod 5, a + c = 2 mod 5. This is because 7 = 2 mod 5. How do I know? Well, 5 | (7 - 2) because 5 | 5. Arithmetic modulo a number works by doing the operation as normal, and then ‘wrapping’ around the number. Here’s how to prove it:
Assume: a = b mod n c = d mod n Then: a = n*k + b c = n*r + d a + c = n*k + n*r + b + d a + c = n(k + r) + b + d Note that k + r is an integer. a + c = b + d mod n —-
A similar proof can show that multiplication and so on still work too. Since arithmetic still works mod n, you can make a lot of cool proofs, or reuse a lot of your knowledge from ordinary arithmetic.
I hope to chach you all next week for more lovely math!