Suppose that \(a\) and \(b\) are non-zero integers. If there exists an integer, \(k\), such that \(b = ak\), then we say that \(a\) divides \(b\), and this is written as,
\[ a \vert b \,.\]More generally, for integers, \(a\), \(b\), \(q\), and \(r\), if \(b\) divides \(a\), written as \(b \vert a\), then,
\[ a = bq + r\,,\]where \(r = 0\). We use \(q\) for quotient and \(r\) for remainder. If \(r \neq 0\), then \(b\) does not divide \(a\), written as \(b \not\vert a\).
For any \(a \neq 0\), \(b \neq 0\), and \(q \neq 0\), we can write any number in the form of \((2)\), e.g.
\[ 11 = 2 \cdot 5 + 1\,. \]By the property of commutativity, we can also write \(11 = 5\cdot 2 + 1\).
We call a natural number \(p\) where \(p > 1\), a prime number if it has exactly two distinct divisors, \(1\) and \(p\).
\(0\) (or nullity) and \(1\) (or unity) are neither prime nor composite.
For any prime number,
\[ 1 \vert p \text{ and } p \vert p \,.\]A composite number is any number which is not prime. Following from these concepts, it is true that all composite numbers can be written as the product of powers of primes.
For any \(n\) which is composite,
\[ n = p_1^{q_1} \cdot p_2^{q_2} \cdot \cdots \cdot p_k^{q_k}\,.\]This is called the Fundamental Theorem of Arithmetic.
For example, the composite numbers up to \(15\) are given as, \(4, 6, 8, 9, 10, 12, 14,\) and \(15\), where,
\[\begin{aligned} 4 &= 2^2 \\ 6 &= 2 \cdot 3 \\ 8 &= 2^3 \\ 9 &= 3^2 \\ 10 &= 2 \cdot 5 \\ 12 &= 2^2 \cdot 3 \\ 14 &= 2 \cdot 7 \\ 15 &= 3 \cdot 5 \\ &\vdots \end{aligned}\]Proposition: If \(a \vert b\) and \(b \vert a\), then \(a = b\).
If \(a\) and \(b\) are integers and \(a\) divides \(b\), then there exists an integer \(k_1\) such that,
\[ b = a \cdot k_1 \,,\]where \(a\) and \(k_1\) are called factors or divisors of \(b\).
If \(b\) also divides \(a\), then by \((7)\),
\[ \begin{aligned} a &= b \cdot k_2 \\ &= a\cdot k_1 \cdot k_2 \\ a - a \cdot k_1 \cdot k_2 &= 0 \\ a( 1 - k_1 \cdot k_2 ) &= 0 \end{aligned}\]By this equation, either \(a\) or \(1 - k_1 \cdot k_2\) are equal to \(0\). Since we have already determined that \(a \neq 0\) and therefore \(k_1\) and \(k_2\) are also non-zero, the product of \(k_1\) and \(k_2\) must be equal to unity. The only way that the product of \(k_1\) and \(k_2\) could be equal to unity is if either \(k_1 = k_2 = 1\) or if \(k_1 = k_2^{-1}\) and \(k_2 = k_1^{-1}\). However, if \(a \cdot k_1 = b \cdot k_2\), then it must follow that \( k_1 = k_2 = 1\) and \(a = b\).
Proposition: For integers \(a\), \(b\), \(d\), \(r\), and \(s\), if \(d\) divides \(a\) and \(d\) divides \(b\), then \(d\) divides \(ra + sb\).
Since \(d\) divides both \(a\) and \(b\), there must exists integers \(k_1\) and \(k_2\) such that \(a = dk_1\) and \(b = dk_2\).
Therefore, \(ra + sb = r d k_1 + s d k_2 = d(r k_1 + s k_2)\) and so \(d\) divides \(ra + sb\).
Furthermore, since \(d\) divides both \(a\) and \(b\), then \(d\) also divides \(a + b\), \(a - b\), \(ra\), and \(sb\).
Proposition: Suppose \(a\), \(b\), and \(c\) are integers, \(a\) divides \(b\) if and only if \(ac\) divides \(bc\).
If \(ac\) divides \(bc\), then \(bc = ac\cdot k_1\) where \(ac\) and \(k_1\) are factors of \(bc\). By the law of cancellation, it must be that \(b = a\cdot k_1\).
Proposition: If \(a\) divides \(b\) and \(b\) divides \(c\), then \(a\) divides \(c\). This is what we call transitivitiy.
If \(a\) divides \(b\), then there exists some \(k_1\) such that \(b = a \cdot k_1\) and if \(b\) divides \(c\), there exists some \(k_2\) such that \(c = b\cdot k_2\). It therefore follows that,
\[ c = b\cdot k_2 = (a\cdot k_1) \cdot k_2\,. \]By the law of associativity, it's clear that \(a\) divides \(c\).