Example Questions Regarding Primes And Composites

# 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)
\begin{align} a^2 = (p_1^{e_1/2}p_2^{e_2/2}...p_k^{e_k/2})^2 \\ a^2 = (p_1^{e_1/2})^2 (p_2^{e_2/2})^2...(p_k^{e_k/2})^2 \\ a^2 = p_1^{e_1}p_2^{e_2}...p_k^{e_k} \end{align}

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.