Elementary Number Theory Problems 3.2 Solution (David M. Burton's 7th Edition)
Background
These are my solutions while I was studying number theory using this book. I will use the theorems and definitions mentioned in the book.
If you don't have the book or are unsure which theorem or definition I am using here, you can check out this article, where I listed all theorems, corollaries, and definitions by following the book's order.
If you haven't heard of this book and are interested in learning number theory, I strongly recommend it since it is quite friendly for beginners. You can check out the book by this link:
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.
All Problems in 3.2 (p. 49 - p. 50)
Q1
Determine whether the integer $701$ is prime by testing all primes $p \leq \sqrt{701}$ as possible divisors. Do the same for the integer $1009$.
Q2
Employing the Sieve of Eratosthenes, obtain all the primes between 100 and 200.
Q3
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.]
Q4
Establish the following facts:
(a) $\sqrt{p}$ is irrational for any prime $p$.
(b) If $a$ is a positive integer and $\sqrt[n]{a}$ is rational, then $\sqrt[n]{a}$ must be an integer.
(c) For $n \geq 2$, $\sqrt[n]{n}$ is irrational.
[Hint: Use the fact that $2^n > n$.]
Q5
Show that any composite three-digit number must have a prime factor less than or equal to $31$.
Q6
Fill in any missing details in this sketch of a proof of the infinitude of primes: Assume that there are only finitely many primes, say $p_{1}, p_{2}, ..., p_{n}$. Let $A$ be the product of any $r$ of these primes and put $B = \frac{p_{1}p_{2}...p_{n}}{A}$. Then each $p_{k}$ divides either $A$ or $B$, but not both. Because $A + B \gt 1$, $A + B$ has a prime divisor different from any of the $p_{k}$, which is a contradiction.
Q7
Modify Euclid's proof that there are infinitely many primes by assuming the existence of a largest prime $p$ and using the integer $N = p! + 1$ to arrive at a contradiction.
Q8
Give another proof of the infinitude of primes by assuming that there are only finitely many primes, say $p_{1}, p_{2}, ..., p_{n}$, and using the following integer to arrive at a contradiction:
$$ N = p_{2}p_{3} \cdots p_{n} + p_{1}p_{3} \cdots p_{n} + \cdots + p_{1}p_{2} \cdots p_{n-1} $$Q9
(a) Prove that if $n \gt 2$, then there exists a prime $p$ satisfying $n \lt p \lt n!$.
[Hint: If $n! - 1$ is not prime, then it has a prime divisor $p$; and $p \leq n$ implies $p \mid n!$, leading to a contradiction.]
(b) For $n \gt 1$, show that every prime divisor of $n! + 1$ is an odd integer that is greater than $n$.
Q10
Let $q_{n}$ be the smallest prime that is strictly greater than $P_{n} = p_{1}p_{2} \cdots p_{n} + 1$. It has been conjectured that the difference $q_{n} - (p_{1}p_{2} \cdots p_{n})$ is always a prime. Confirm this for the first five values of $n$.
Q11
If $p_{n}$ denotes the $n$th prime number, put $d_{n} = p_{n+1} - p_{n}$. An open question is whether the equation $d_{n} = d_{n + 1}$ has infinitely many solutions. Give five solutions.
Q12
Assuming that $p_{n}$ is the $n$th prime number, establish each of the following statements:
(a) $p_{n} > 2n - 1$ for $n \geq 5$.
(b) None of the integers $P_{n} = p_{1}p_{2} \cdots p_{n} + 1$ is a perfect square.
[Hint: Each $P_{n}$ is of the form $4k + 3$ for $n \gt 1$.]
(c) The sum
is never an integer.
Q13
For the repunits $R_{n}$, verify the assertions below:
(a) If $n \mid m$, then $R_{n} \mid R_{m}$.
[Hint: If $m = kn$, consider the identity $$x^{m} - 1 = (x^{n} - 1)(x^{(k - 1)n} + x^{(k - 2)n} + ... + x^{n}+ 1).]$$
(b) If $d \mid R_{n}$ and $d \mid R_{m}$, then $d \mid R_{n+m}$.
[Hint: Show that $R_{m+n} = R_{n}10^{m} + R_{m}$.]
(c) If $gcd(n, m) = 1$, then $gcd(R_{n}, R_{m})= 1$.
Q14
Use the previous problem to obtain the prime factors of the repunit $R_{10}$.