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!