# Divisors and Things

This week we talked about how to prove things about numbers that evenly divide other numbers.

### X divides Y

`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!