# 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 (7776^{2}) and fifth power (36^{5}).

## 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 (2744^{2}), and is a cube (196^{3}).

## 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.