Elementary Number Theory - 1 Problems

1. Suppose that \(a,b,c \in \mathbb{N}\). Prove each of the following:
• If \(a|b\) and \(b|c\), then \(a|c\).
• Since \(a|b\) and \(b|c\), we have \(b= ak_1\) and \(c = b k_2\) where \(k_1,k_2 \in \mathbb{Z}\). Hence, we get \(c = b k_2 = a k_1 k_2 = a (k_1 k_2)\). Since \(k_1,k_2 \in \mathbb{Z}\), we get \(k_1 k_2 \in \mathbb{Z}\). Hence, we get \(a | c\).
• If \(a|b\) and \(a|c\), then \(a| (bx+cy)\) for every \(x,y \in \mathbb{Z}\).
• Since \(a|b\) and \(a|c\), we have \(b = a k_1\) and \(c = a k_2\) where \(k_1,k_2 \in \mathbb{Z}\). Hence, \(bx + cy = a k _1 x + a k_2 y = a \left(k_1 x + k_2 y \right)\). Note that since \(k_1,k_2,x,y \in \mathbb{Z}\), we have \(k_1 x + k_2 y \in \mathbb{Z}\). Hence, we get \(a | \left( bx + cy \right)\).
2. Prove that if \(n \in \mathbb{N}\) is composite, then it has a prime factor not exceeding \(\sqrt{n}\).
• Let \(n = p_1 p_2 \ldots p_r\) where \(p_i\)'s are prime not necessarily distinct. Further we are given that \(n\) is composite. Hence, we have \(r \geq 2\). Now assume the contrary that all the prime factors of \(n\) exceed \(\sqrt{n}\) i.e. \(p_k > \sqrt{n}\), \(\forall k \in \{1,2,\ldots,r \}\). Then \(n = p_1 p_2 \ldots p_r > \left(\sqrt{n} \right)^r = n^{r/2}\). Hence, we have \(n > n^{r/2}\). This implies \(r < 2\). This contradicts the fact that \(r \geq 2\). Hence there is at-least one prime factor not exceeding \(\sqrt{n}\).
3. Prove that \(n^4 + 4\) is composite for every natural number \(n > 1\).
• \(n^4 + 4 = n^4 + 4n^2 + 4 - 4n^2 = \left(n^2+2 \right)^2 - \left( 2n \right)^2 = \left( n^2+ 2 + 2n \right) \left( n^2 + 2 - 2n\right)\). Note that \(n^2+2 + 2n > n^2 + 2 -2n\), \(\forall n \in \mathbb{N}\). For \(n > 1\), we have \(n^2 + 2 -2n = (n-1)^2 + 1 > 1\). Hence, \(n^4 +4 = \left( n^2+ 2 + 2n \right) \left( n^2 + 2 - 2n\right)\) where \(\left( n^2+ 2 + 2n \right) \in \mathbb{Z}\) and \(\left( n^2 + 2 - 2n\right) \in \mathbb{Z}\). Further for \(n > 1\), we have \(\left( n^2+ 2 + 2n \right) > \left( n^2+ 2 - 2n \right) > 1\). Hence, \(n^4 +4\) is a product of two natural numbers greater than \(1\). Hence, \(n^4+4\) is composite for every natural number \(n > 1\).