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!