Elementary Number Theory - 1.2 Definitions and Propositions

Definition: We say \(a \in \mathbb{Z}^+\) and \(a \gt 1\) is an irreducible if it has exactly two positive divisors, namely \(1\) and \(a\).
Definition: We say \(p \in \mathbb{Z}^+\) and \(p \gt 1\) is a prime if \(p | ab \implies p | a\) (or) \(p | b\).
Definition: We say \(a \in \mathbb{Z}^+\) and \(a \gt 1\) is composite if \(a\) is not a prime.


Proposition:
\(p\) is a prime if and only if \(p\) is irreducible.

Proof:

• We shall first prove that "If \(p\) is a prime, then \(p\) is an irreducible".
• If \(p\) is not irreducible, then \(p=ab\) for some \(a,b \in \mathbb{Z}^+\) where \(1 \lt a,b \lt p\). Clearly, \(p|p\) i.e. \(p|ab\) but \(p\not | a\) and \(p\not | b\) since \(1 \lt a,b \lt p\). Hence, \(p\) is not a prime.
• We shall now prove that "If \(p\) is an irreducible, then \(p\) is a prime".
• If \(p\) is an irreducible, we shall prove that if \(p\not | a\) and \(p\not | b\), then \(p\not ab\). Since \(p\) is an irreducible, the divisors of \(p\) are \(1\) and \(p\). Since \(p\not | a\) and \(p\not | b\), we have \((p,a) = 1\) and \((p,b) = 1\). Hence, we get \(ax_1 + py_1 = 1\) and \(bx_2 + py_2 = 1\). Multiplying out the two, we get \((ax_1 + py_1)(bx_2 + py_2) = 1\). i.e. we get \(abx_1x_2 + p(ax_1y_2 + bx_2y_1 + py_1 y_2) = 1\). Hence, we get that \((ab,p) = 1\). Hence, we have that \(p\not| ab\). Hence, \(p\) is a prime.

Proposition:

Suppose that \(a_1,a_2,\ldots,a_k \in \mathbb{Z}\), and \(p\) is a prime. If \(p | a_1a_2\ldots a_k\), then \(p|a_j\) for some \(j \in \{1,2,\ldots,k\}\).

Proof:

The proof follows immediately from the previous proposition and induction. Since \(p\) is a prime, it divides either \(a_1\) (or) \(a_2a_3 \ldots a_k\) and then get the rest by simple induction.

Proposition (Fundamental Theorem of Arithmetic):

Every natural number \(n > 1\) is representable as a product of primes, uniquely up to the order of factors.

Proof:
First, we shall prove by induction that any natural number is a product of prime(s). Let \(P(n)\) be the statement that \(n+2\) can be written as a product of prime(s). Let \(S = \{n \in \mathbb{N}: P(n) \text{ is true }\}\). Clearly, \(0 \in S\). This is so since \(2\) is a prime and can be written as \(2=2\). Assume that all natural numbers up-to \(k\) is in \(S\). Now consider \(k+1\). If \(k+3\) is irreducible, we proved that it is a prime and hence \(k+3 = k+3\). If \(k+3\) is not an irreducible, then we have \(k+3 = ab\), where \(1 \lt a,b \lt k+3\). Now by induction hypothesis, since \(1 \lt a,b \leq k+2\), we have \(a\), \(b\) to be product of primes i.e. \(a = p_1p_2 \ldots p_l\) and \(b = p_{l+1} p_{l+2} \ldots p_{l+m}\) where \(p_i\) are primes. Hence, \(k+3 = ab = p_1 p_2 \ldots p_l p_{l+1} p_{l+2} \ldots p_{l+m}\). Hence, \(k+3\) can also be expressed as a product of primes. Hence, \(k+1 \in S\). By principle of mathematical induction, we have that every natural number. Hence, every natural number is representable as a product of primes.
We still needs to prove uniqueness. Assume that the representation is not unique i.e. let \(n=p_1 p_2 \ldots p_l = q_1 q_2 \ldots q_k\). Consider \(p_1\). We have \(p_1 | n\). This means that \(p_1 | \prod_{j=1}^{k} q_j\) and from the definition of a prime we get \(p_1 | q_j\) for some \(j\). From the definition of a prime, we get that \(p_1 | q_j\). But from an earlier proved proposition since \(q_j\) is a prime, the only factors of \(q_j\) are \(1\) and \(q_j\) itself. This gives us \(p_1 = q_j\). Repeat this argument a finite number of times to conclude that \(l = k\) and get the desired result.

Proposition:
Every natural number \(n > 1\) is uniquely representable in the form \[n = p_1^{\alpha_1} p_2^{\alpha_2} \ldots p_k^{\alpha_k}\] where \(p_1 < p_2 < \cdots \lt p_k\) are primes and \(\alpha_k \in \mathbb{Z}^+\).

Proof:
Follows immediately from the above proposition and grouping together equal primes. The above is the canonical prime decomposition of a natural number \(n\).