Section 8.5 Finding divisors via FTA
If we know the prime decompositions of two integers \(m\) and \(n\text{,}\) it is easy to tell whether \(m\) divides \(n\text{:}\)
Theorem 8.5.1.
Let \(n=p_1^{a_1}\cdots p_k^{a_k}\) be a prime decomposition (i.e. \(p_i\)s are prime, \(p_1\lt \cdots \lt p_k\text{,}\) and \(a_i>0\)). Then \(m\) divides \(n\) if, and only if:
Proof.
-
(\(\impliedby\)): If (8.5.1) holds, then
\begin{equation*} n=m \cdot p_1^{b_1-a_{1}}\cdots p_k^{b_k-a_{k}} \;\;\; \Longrightarrow \;\;\; m \text{ divides } n\text{.} \end{equation*} -
(\(\implies\)): Suppose \(m\) divides \(n\text{,}\) then \(n=mc\) fr some positive integer \(c\text{.}\) Then \(m\) and \(n\) have prime decompositions whose product is the prime decomposition for \(n\) as shown below:
\begin{equation*} \underbrace{p_1^{a_1}\cdots p_k^{a_k}}_n = \underbrace{q_1^{c_1}\cdots q_l^{c_l}}_m\underbrace{r_1^{d_1}\cdots r_s^{d_s}}_c\text{.} \end{equation*}The FTA implies each \(q_i\) and \(r_i\) equals to some \(p_j\text{.}\) To ease notation, we'll assume \(q_{i}=r_{i}=p_{i}\) for all \(i\text{,}\) but that \(c_{i}=0\) if \(p_{i}\) didn't appear as one of the primes \(q_{i}\) originally, and similarly for the \(d_{i}\text{.}\) Then the product above is in fact
\begin{equation*} \underbrace{p_1^{a_1}\cdots p_k^{a_k}}_n = {q_1^{c_1}\cdots q_l^{c_l}}{r_1^{d_1}\cdots r_s^{d_s}} =p_{1}^{c_{1}+d_{1}}\cdots p_{k}^{c_{k}+d_{k}}\text{.} \end{equation*}The FTA now implies each power \(c_i+d_i\) equals to \(a_j\text{.}\) In particular, this means \(m=p_{1}^{c_{1}}\cdots p_{k}^{c_{k}}\) where \(0\leq c_{k}\leq a_{k}\text{.}\)
Example 8.5.2.
What are all the divisors of \(360\text{?}\)
First, we find the prime factorization of \(360\text{:}\) we can see that \(36=4\cdot 9=2^2\cdot 3^2\text{,}\) and so \(360 = 10\cdot 2^2\cdot 3^2 = 2^3\cdot 3^2\cdot 5\text{.}\) To list all the divisors, we just have to look at the values \(2^j\cdot 3^{k}\cdot 5^{\ell}\) where \(0\leq j\leq 3\text{,}\) \(0\leq k\leq 2\text{,}\) and \(0\leq \ell\leq 1\text{.}\) The possible powers of \(2\) are \(1, \; 2, \; 4, \; 8\text{,}\) and the possible powers of \(3\) are \(1,3,9\text{,}\) so we multiply the powers of two by these to get
The possible powers of \(5\) are just \(1\) and \(5\text{,}\) so we can just multiply these numbers by \(1\) and \(5\) to get