Divides

an integer $$ n$$ is divisible by another integer $$ m$$ if there exists an integer $$ k$$ such
that $$ n=k\cdot m$$. If this is all true we write $$ m|n$$.

Divisible iff Integer Quotient

Suppose that $$ a\mid b$$ iff $$ \frac{b}{a}\in \mathbb{Z}$$

Suppose that $$ a\mid b$$, then there is some $$ k\in \mathbb{Z}$$ such that $$ a\cdot k=b$$
therefore $$ k=\frac{b}{a}$$, and since $$ k\in \mathbb{Z}$$ then $$ \frac{b}{a}\in \mathbb{Z}$$ as needed.

n Factorial is Divisible by Its Factors

For any $$ k\in [1,\dots ,n]$$
$$$k\mid n!$$$

$$$n!=1\cdots k\cdots n$$$
therefore
$$$\frac{n!}{k}=1\cdots \left(\frac{k}{k}\right)\cdots n\in \mathbb{Z}$$$
so therefore $$ k\mid n!$$

Not Divisible iff Non-Integer Quotient

$$ a\nmid b$$ iff $$ \frac{b}{a}\notin \mathbb{Z}$$

By the fact that $$ P\phantom{\rule{thickmathspace}{0ex}}\u27fa\phantom{\rule{thickmathspace}{0ex}}Q$$ iff $$ \mathrm{\neg}P\phantom{\rule{thickmathspace}{0ex}}\u27fa\phantom{\rule{thickmathspace}{0ex}}\mathrm{\neg}Q$$

1 Divides Everything

Suppose that $$ j\in \mathbb{Z}$$, then $$ 1|j$$

In the definition of
divides take $$ k=j$$, then we can see that $$ j=j\cdot 1$$ thus we can say that $$ 1|j$$

If something Divides One then it is One or Negative One

Suppose $$ d\mid 1$$ then $$ d=\pm 1$$

We have that $$ 1=kd$$ but the only numbers in $$ \mathbb{Z}$$ that have a multiplicative inverse are $$ 1,-1$$ so $$ d$$ must be one of those or else we have a contradiction.

If Zero Divides a Number, then that Number is Zero

Suppose $$ 0\mid d$$ then $$ d=0$$

By definition we have $$ d=k\cdot 0=0$$ so $$ d=0$$

0 is Divisible by Everything

for any $$ d\in \mathbb{Z},d|0$$

In the definition of divides take $$ k=0$$,
then we can see that $$ 0=0\cdot d$$ thus we can say that $$ d|0$$

Everything Divides Itself

Let $$ a\in \mathbb{Z}$$ then $$ a\mid a$$

Clearly $$ 1\cdot a=a$$ therefore $$ a\mid a$$

Division is Transitive

Suppose $$ a\mid b$$ and $$ b\mid c$$ then $$ a\mid c$$

We have that $$ b={k}_{a}a$$ and $$ c={k}_{b}b$$ therefore $$ c={k}_{b}\left({k}_{a}a\right)$$ therefore by taking $$ {k}_{c}=\left({k}_{a}{k}_{b}\right)$$ we see that $$ a\mid c$$

If you Divide a Number, then You Divide their Multiples

For any $$ a,b,c\in \mathbb{Z}$$
$$$a\mid b\phantom{\rule{thickmathspace}{0ex}}\u27f9\phantom{\rule{thickmathspace}{0ex}}a\mid bc$$$

Suppose that $$ a\mid b$$ therefore there is $$ k\in \mathbb{Z}$$ such that $$ b=ka$$, therefore multiply both sides to get $$ bc=\left(kc\right)a$$ and therefore $$ a\mid bc$$ as needed.

If it Divides it's Less than or Equal with Absolute Values

Suppose that $$ n,d\in \mathbb{Z}$$, such that $$ n\ne 0$$ then if $$ d$$ divides $$ n$$, then $$ |d|\le |n|$$

We see that $$ n=kd$$ for some $$ k\in \mathbb{Z}$$, since $$ n\ne 0$$ then also we must have $$ k,d\ne 0$$ specifically note that $$ |k|\ge 1$$ so that we have $$$|n|=|kd|=|k|\cdot |d|\ge 1|d|=|d|$$$ so that $$ |n|\ge |d|$$

We have to specify $$ n\ne 0$$ because we know that everything divides zero, and therefore without that assumption we could use it to claim that since $$ -42\mid 0$$ that $$ |-42|\le 0$$ which is clearly false.

Larger Absolute value Implies no Division

for any $$ n,d\in \mathbb{Z}$$ such that $$ n\ne 0$$ if $$ |d|>|n|$$ then $$ d\nmid n$$

This follows by the contrapositive and this

If two Numbers Divide each other then Their Absolute Values are Equal

For any $$ a,b\in \mathbb{Z}$$, if $$ a\mid b$$ and $$ b\mid a$$ then $$ |a|=|b|$$

If $$ a=0$$ then because $$ a\mid b$$ then this forces $$ b=0$$ so that $$ a=b=0$$, also if we assumed $$ b=0$$ the same thing occurs.

In the case that neither of $$ a,b=0$$ then recall that if $$ a\mid b$$ we have $$ |a|\le |b|$$ also since $$ b\mid a$$ then also $$ |a|\le |b|$$ so that $$ |a|=|b|$$.

If a Number Divides another Then Given a Common Factor Their Quotients Divide Each Other

Suppose that $$ a,b,d\in {\mathbb{N}}_{1}$$ such that $$ a\mid b$$ and that $$ d$$ is a common divisor of $$ a,b$$, then
$$$\frac{a}{d}\mid \frac{b}{d}$$$

Divisibility is a Partial Order on the Natural Numbers

Divisibility is a partial order on $$ {\mathbb{N}}_{0}$$.

It is reflexive because we know that everything divides itself, we know it is transitive, and we also know that it is anti-symmetric, because for any $$ n\in {\mathbb{N}}_{0},|n|=n$$ and using this proposition.

Note that we can't quite get a partial order $$ \mathbb{Z}$$ because of the fact that $$ -a\mid a$$.

Linearity of Division

Suppose that $$ a\mid {b}_{1},\dots ,{b}_{n}$$ then
$$$a\mid {c}_{1}{b}_{1}+\cdots +{c}_{n}{b}_{n}$$$
where $$ a,{b}_{i},{c}_{i}\in \mathbb{Z}$$

For the base case of $$ n=2$$ if $$ a\mid {b}_{1}$$ and $$ a\mid {b}_{2}$$ then we know that there are $$ {k}_{1},{k}_{2}\in \mathbb{Z}$$ such that $$ {b}_{1}={k}_{1}a$$ and $$ {b}_{2}={k}_{2}a$$ so that $$ {c}_{1}{b}_{1}+{c}_{2}{b}_{2}={c}_{1}\left({k}_{1}a\right)+{c}_{2}\left({k}_{2}a\right)=a({c}_{1}{k}_{1}+{c}_{2}{k}_{2})$$.

For the induction step, assume the statement holds true for $$ k\in {\mathbb{N}}_{1}$$ and we'll show that it holds true for $$ k+1$$ so suppose that $$ a\mid {b}_{1},\dots {b}_{k+1}$$ by the induction hypothesis we know that $$ a\mid {c}_{1}{b}_{1}+\cdots +{c}_{k}{b}_{k}$$ so we get some $$ {j}^{\mathrm{\prime}}\in \mathbb{Z}$$ such that $$ {c}_{1}{b}_{1}+\cdots +{c}_{k}{b}_{k}={j}^{\mathrm{\prime}}a$$ and also some $$ {j}^{\mathrm{\prime}\mathrm{\prime}}\in \mathbb{Z}$$ such that $$ {b}_{k+1}={j}^{\mathrm{\prime}\mathrm{\prime}}a$$ and therefore $$${c}_{1}{b}_{1}+\cdots +{c}_{k}{b}_{k}+{c}_{k+1}{b}_{k+1}={j}^{\mathrm{\prime}}a+{j}^{\mathrm{\prime}\mathrm{\prime}}a=a({j}^{\mathrm{\prime}}+{j}^{\mathrm{\prime}\mathrm{\prime}})$$$ so therefore $$ a\mid {c}_{1}{b}_{1}+\cdots +{c}_{k+1}{b}_{k+1}$$

Even Number

We say that an integer $$ n\in \mathbb{Z}$$ is even if there is some $$ k\in \mathbb{Z}$$ such that
$$$n=2k$$$

A power of an Even Number is Even

If $$ n\in \mathbb{Z}$$ is even, then for any $$ m\in {\mathbb{N}}_{1}$$ we have $$ {n}^{m}$$ is even

If $$ n$$ is even then there is some $$ k\in \mathbb{Z}$$ such that $$ n=2k$$ and therefore $$ {n}^{m}={\left(2k\right)}^{m}={2}^{m}{k}^{m}=2\left({2}^{m-1}{k}^{m}\right)$$ so that $$ {n}^{m}$$ is also even.

Odd Number

We say that an integer $$ n\in \mathbb{Z}$$ is odd if there is some $$ k\in \mathbb{Z}$$ such that
$$$n=2k+1$$$

A power of an Even Number is Odd

If $$ n\in \mathbb{Z}$$ is odd, then for any $$ m\in {\mathbb{N}}_{0}$$ we have $$ {n}^{m}$$ is odd

Base case, set $$ m=0$$ then $$ {n}^{m}=1$$ which is odd. For the induction step assume it holds true for $$ k\in {\mathbb{N}}_{0}$$ so that $$ {n}^{k}$$ is odd, which means that there is some $$ j\in \mathbb{Z}$$ such that $$ {n}^{k}=2j+1$$ therefore $$ {n}^{k+1}=(2j+1)n$$ but $$ n$$ is odd so there is some $$ {j}^{\mathrm{\prime}}\in \mathbb{Z}$$ such that $$ n=2{j}^{\mathrm{\prime}}+1$$ and thus $$${n}^{k+1}=(2j+1)(2{j}^{\mathrm{\prime}}+1)=4j{j}^{\mathrm{\prime}}+2j+2{j}^{\mathrm{\prime}}+1=2(2j{j}^{\mathrm{\prime}}+j+{j}^{\mathrm{\prime}})+1$$$ hence $$ {n}^{k+1}$$ is prime so the statement follows from the principle of induction.

Product of Two Equal Factors means They are Square Roots

Suppose that $$ a=bc$$ then $$ b=\sqrt{a}$$ iff $$ b=c$$

$$ \phantom{\rule{thickmathspace}{0ex}}\u27f9\phantom{\rule{thickmathspace}{0ex}}$$ suppose that $$ b=\sqrt{a}$$ then for sake of contradiction if $$ b\ne c$$ then if $$ c<b$$ then we see that $$ a=bc<bb=\sqrt{a}\sqrt{a}=a$$ which is impossible, on the other hand if $$ c>b=\sqrt{a}$$ then we see $$ a=bc<cc<\sqrt{a}\sqrt{a}$$ which yields the same contradiciton.

$$ \phantom{\rule{thickmathspace}{0ex}}\u27f8\phantom{\rule{thickmathspace}{0ex}}$$ Now suppose that $$ b=c$$ therefore $$ a=bc=bb$$ therefore $$ {b}^{2}=a$$ and so $$ b=\sqrt{a}$$ as needed, moreover in this case note that $$ c=\sqrt{a}$$ as well.

Product Implies Square Root bound on Factors

Suppose that $$ a,b,c\in {\mathbb{N}}_{1}$$ and that $$ b\ne c$$ where $$ a=bc$$ then
$$$(b>\sqrt{a}\wedge c<\sqrt{a})\vee (b<\sqrt{a}\wedge c>\sqrt{a})$$$

Suppose for the sake of contradiction that it was not true, so that we knew that
$$$(b\le \sqrt{a}\vee c\ge \sqrt{a})\wedge (b\ge \sqrt{a}\vee c\le \sqrt{a})$$$
Suppose that $$ b\le \sqrt{a}$$ and $$ b\ge \sqrt{a}$$ holds true, then $$ b=\sqrt{a}$$ since $$ c\ne b$$ then if $$ c<b$$ we see that $$ bc<\sqrt{a}\sqrt{a}=a$$ which is a contradiction since we know that $$ bc=a$$, if it turns out that $$ c\le \sqrt{a}$$ and $$ c\ge \sqrt{a}$$ it is handeled symetrically.

On the other hand if we know that $$ b\le \sqrt{a}$$ and that $$ c\le \sqrt{a}$$, since $$ b\ne a$$ then we know that $$ b\ne \sqrt{a}$$, therefore more specifically we see that $$ b<\sqrt{a}$$ this implies that $$ a=bc<\sqrt{a}\sqrt{a}=a$$ which is a contradiction. In the case of $$ c\ge \sqrt{a}$$ and $$ b\ge \sqrt{a}$$ it follows in a symmetrical manner.

Number To the Power m Minus 1 Divides Number To the Power n if m Divides n

Let $$ a,m,n\in {\mathbb{N}}_{1}$$ then
$$$m\mid n\phantom{\rule{thickmathspace}{0ex}}\u27f9\phantom{\rule{thickmathspace}{0ex}}({a}^{m}-1)\mid ({a}^{n}-1)$$$

We have that $$ n=mk$$ for some $$ k\in \mathbb{Z}$$ and we want to prove that $$ {a}^{mk}-1=({a}^{m}-1)j$$ for some $$ j\in \mathbb{Z}$$, a good guess would be that $$ j={a}^{(m-1)k}$$ which produces $$ ({a}^{m}-1)\left({a}^{(m-1)k}\right)={a}^{mk}-{a}^{(m-1)k}$$ and so we have to get rid of the $$ {a}^{(m-1)k}$$ term, which inspires us to try $$ j={a}^{(m-1)k}+{a}^{(m-2)k}$$ which yields $$$({a}^{m}-1)({a}^{(m-1)k}+{a}^{(m-2)k})={a}^{km}+{a}^{(m-1)k}-({a}^{(m-1)k}+{a}^{(m-2)k})={a}^{km}-{a}^{(m-2)k}$$$

As we've just run into the same problem as last time we see that adding $$ {a}^{(m-3)k}$$ would remove the most recent residue term, but then leave the new residue term $$ {a}^{(m-3)k}$$ . Therefore formally using induction we can show that $$$({a}^{m}-1)\left(\sum _{i=0}^{m-1}{a}^{ik}\right)={a}^{mk}-1={a}^{n}-1$$$ where $$ 1$$ is really the residue term $$ {a}^{\left(0\right)k}$$