# 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{n}$, show that $n \gt 1$ is either a prime or the product of two primes. "

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{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{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{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

MathNumber TheorySolution