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.

Not Divisible iff Non-Integer Quotient

\( a \nmid b \) iff \( \frac{b}{a} \notin \mathbb{ Z } \)

By the fact that \( P \iff Q \) iff \( \neg P \iff \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 = k d \) 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 \implies a \mid b c
\]

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 \neq 0 \) then if \( d \) divides \( n \), then \( \lvert d \rvert \le \lvert n \rvert \)

We see that \( n = k d \) for some \( k \in \mathbb{ Z } \), since \( n \neq 0 \) then also we must have \( k, d \neq 0 \) specifically note that \( \lvert k \rvert \ge 1 \) so that we have \[ \lvert n \rvert = \lvert k d \rvert = \lvert k \rvert \cdot \lvert d \rvert \ge 1 \lvert d \rvert = \lvert d \rvert \] so that \( \lvert n \rvert \ge \lvert d \rvert \)

We have to specify \( n \neq 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 \( \lvert -42 \rvert \le 0 \) which is clearly false.

Larger Absolute value Implies no Division

for any \( n, d \in \mathbb{ Z } \) such that \( n \neq 0 \) if \( \lvert d \rvert \gt \lvert n \rvert \) 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 \( \lvert a \rvert = \lvert b \rvert \)

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 \( \lvert a \rvert \le \lvert b \rvert \) also since \( b \mid a \) then also \( \lvert a \rvert \le \lvert b \rvert \) so that \( \lvert a \rvert = \lvert b \rvert \).

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, \lvert n \rvert = 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, \ldots , 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 \left( c _ 1 k _ 1 + c _ 2 k _ 2 \right) \).

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, \ldots 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 ^ \prime \in \mathbb{ Z } \) such that \( c _ 1 b _ 1 + \cdots + c _ k b _ k = j ^ \prime a \) and also some \( j ^ { \prime \prime } \in \mathbb{ Z } \) such that \( b _ { k + 1 } = j ^ { \prime \prime } a \) and therefore \[ c _ 1 b _ 1 + \cdots + c _ k b _ k + c _ { k + 1 } b _ { k + 1 } = j ^ \prime a + j ^ { \prime \prime } a = a \left( j ^ \prime + j ^ { \prime \prime } \right) \] 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 } = \left( 2 j + 1 \right) n \) but \( n \) is odd so there is some \( j ^ \prime \in \mathbb{ Z } \) such that \( n = 2 j ^ \prime + 1 \) and thus \[ n ^ { k + 1 } = \left( 2 j + 1 \right) \left( 2 j ^ \prime + 1 \right) = 4j j ^ \prime + 2j + 2 j ^ \prime + 1 = 2 \left( 2 j j ^ \prime + j + j ^ \prime \right) + 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 \)

\( \implies \) suppose that \( b = \sqrt{ a } \) then for sake of contradiction if \( b \neq c \) then if \( c \lt b \) then we see that \( a = b c \lt b b = \sqrt{ a } \sqrt{ a } = a \) which is impossible, on the other hand if \( c \gt b = \sqrt{ a } \) then we see \( a = b c \lt c c \lt \sqrt{ a } \sqrt{ a } \) which yields the same contradiciton.

\( \impliedby \) Now suppose that \( b = c \) therefore \( a = b c = b b \) 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 \neq c \) where \( a = b c \) then
\[
\left( b \gt \sqrt{ a } \land c \lt \sqrt{ a } \right) \lor \left( b \lt \sqrt{ a } \land c \gt \sqrt{ a } \right)
\]

Suppose for the sake of contradiction that it was not true, so that we knew that
\[
\left( b \le \sqrt{ a } \lor c \ge \sqrt{ a } \right) \land \left( b \ge \sqrt{ a } \lor c \le \sqrt{ a } \right)
\]
Suppose that \( b \le \sqrt{ a } \) and \( b \ge \sqrt{ a } \) holds true, then \( b = \sqrt{ a } \) since \( c \neq b \) then if \( c \lt b \) we see that \( b c \lt \sqrt{ a } \sqrt{ a } = a \) which is a contradiction since we know that \( b c = 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 \neq a \) then we know that \( b \neq \sqrt{ a } \), therefore more specifically we see that \( b \lt \sqrt{ a } \) this implies that \( a = b c \lt \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.