Elementary Number Theory Problems 3.3 Solution (David M. Burton's 7th Edition) - Q27


Background

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

Theorems and Corollaries in Elementary Number Theory (Ch 1 - 3)
All theorems and corollaries mentioned in David M. Burton’s Elementary Number Theory are listed by following the book’s order. (7th Edition) (Currently Ch 1 - 3)

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

Question

Prove that for every $n \geq 2$ there exists a prime $p$ with $p \leq n < 2p$.
[Hint: In the case where $n = 2k + 1$, then by the Bertrand conjecture there exists a prime $p$ such that $k < p < 2k$.]

Solution

By Theorem 2.1 Division Algorithm, we can write $n$ in the form of $2k$ or $2k + 1$ for some integer $k$.

When $n = 2k + 1$:

By Bertrand conjecture, there exists a prime $p$ such that $k < p < 2k$. We have $p < 2k < 2k + 1 = n$. Because $k < p$, then we know $2k < 2p$ which implies that $2k + 1 \leq 2p$. As $2k + 1$ is odd and $2p$ is even, $2k + 1 < 2p$, which is $n < 2p$.

So, $p < n < 2p$ when $n = 2k + 1$.

When $n = 2k$:

By Bertrand conjecture, there exists a prime $p$ such that $k < p < 2k$. $p < 2k$ implies that $p < n$. Because $k < p$, we have $2k < 2p$, which means $n < 2p$.

So, $p < n < 2p$ when $n = 2k$.


Read More: All My Solutions for This Book

< Chapter 3.3, Q26 Chapter 3.3, Q28 >