Examples Using Unique Factorization
Before we look at the following examples, let's first remember some key points:
- A number p is considered prime if it only has only 1 and p as its positive divisors.
- Every positive integer greater than 1 is divisible by a prime.
- There exists infinitely many primes.
- If p is a prime and p | ab, then p | a, or p | b, or both.
- A number c that is composite can be written in the form $n = ab$ where 1 < a, b < n
- If c is composite, then it has a prime divisor d such that $1 < d ≤ \sqrt{c}$.
- All integers n can be expressed as a product of primes known as the prime power decomposition, that is $n = p_1^{e_1}p_2^{e_2}...p_k^{e_k}$.
Example 1
Show that for n > 0, the product $n(n + 1)$ is never a square.
We can show this by noting that $n^2 < n(n+1) < (n + 1)^2$ for all n > 0. Hence n(n+1) cannot be a square.
Example 2
Show that an odd integer n cannot be written as a sum of two twin primes.
We know that all primes except 2 are odd. The pair (p, p+2) where both p and p + 2 are primes starts when p = 3. Hence all pairs of twin primes have p ≥ 3 (and hence we exclude the prime 2). Since both p and p + 2 are odd, it follows that their sum is even. Hence if n is odd, then n cannot be written as a product of two twin primes.
Example 3
Show that for a prime p, $(p, n) = 1$ where 1 ≤ n < p.
We note that the only positive divisors of a prime p are 1 and p. Since 1 ≤ n < p, it follows that n is not a multiple of p, and hence (p, n) = 1.
Example 4
Show that if each exponent in the prime power decomposition of n is even, then n is a square.
Suppose that $n = p_1^{e_1}p_2^{e_2}...p_k^{e_k}$ where $e_1, e_2, ..., e_k$ are even. Hence all of the exponents are divisible by 2. Hence suppose that $a = p_1^{e_1/2}p_2^{e_2/2}...p_k^{e_k/2}$, then it follows that:
(1)Hence $n = a^2$, and thus n is a square.
Example 5
Find the smallest integer n divisible by both 2 and 3 that is also a square and fifth power.
Suppose n is divisible by both 2 and 3. Hence 2 and 3 appear in the prime power decomposition of n. Furthermore, if n is both a square and a fifth power and $n = p_1^{e_1}p_2^{e_2}...p_k^{e_k}$, then $e_1, e_2, ..., e_k$ are all divisible by 2 and are all divisble by 5. Hence all these exponents are divisible by 10. Given this, we can let $p_1 = 2$, and $p_2 = 3$, and let $n = 2^{10} \cdot 3^{10} = 60466176$. Hence 60466176 is the smallest integer divisible by 2, 3, and is both a square (77762) and fifth power (365).
Example 6
Find the smallest integer n divisible by 14 that is also a square and a cube.
We will solve this problem similarly to that in example 5. First, we note that if n is divisible by 10, then 2 and 7 appear in the prime power decomposition of n. Furthermore, if $n = p_1^{e_1}p_2^{e_2}...p_k^{e_k}$, then $e_1, e_2, ..., e_k$ are all divisible by 2 and 3. Hence all of these exponents are divisible by 6. Given this, we can let $p_1=2$, $p_2 = 7$, and let $n = 2^6 \cdot 7^6 = 7529536$. Hence 7529536 is the smallest integer n divisible by 14, is a square (27442), and is a cube (1963).
Example 7
Show that it is not possible for a prime p to divide both n and n + 1 for n > 1.
Suppose that p | n. Then n is a multiple of p, that is n = pk for some p. But then, p does not divide n + 1, since p cannot divide pk + 1 since pk + 1 cannot be a multiple of p.
Now suppose that p | n + 1. Then n + 1 = pk, and n = pk - 1. Once again, p cannot divide n, since pk - 1 is not a multiple of p.
Hence if p is prime, then p cannot divide both n and n + 1.