# Elementary Number Theory Problems 3.2 Solution (David M. Burton's 7th Edition) - Q3

My Solution for "Given that $p \not \mid n$ for all primes $p \leq \sqrt[3]{n}$, show that $n \gt 1$ is either a prime or the product of two primes. "

## Table of Contents

This is my solution for Chapter 3.2 Q3 in the book *Elementary Number Theory 7th Edition* written by David M. Burton.

## Background

All theorems, corollaries, and definitions listed in the book's order:

**I will only use theorems or facts that are proved before this chapter**. So you will not see that I quote theorems or facts from the later chapters.

## Question

Given that $p \not \mid n$ for all primes $p \leq \sqrt[3]{n}$, show that $n \gt 1$ is either a prime or the product of two primes.

[Hint: Assume to the contrary that $n$ contains at least three prime factors.]

## Solution

Assume to the contrary that $n$ contains at least three prime factors. We can write $n = p_{1}p_{2}p_{3}d$ where $p_{1}, p_{2}$, and $p_{3}$ are all primes and $d \geq 1$.

We know $p \not \mid n$ for all primes $p \leq \sqrt[3]{n}$, and we know $p_{1}, p_{2}$, and $p_{3}$ can all divide $n$. So, $p_{1}, p_{2}$, and $p_{3}$ are all $\gt \sqrt[3]{n}$. So, $p_{1}p_{2}p_{3} \gt n$. Then $nd \lt p_{1}p_{2}p_{3}d = n$. This means $nd \lt n$, which is a contradiction.

**Read More:** All My Solutions for This Book

## Related Pages

### Ranblog Newsletter

Join the newsletter to receive the latest updates in your inbox.