Elementary Number Theory Problems 3.1 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 and are not sure which theorem or definition I am using here, you can check this article, where I listed all theorems, corollaries, and definitions by following 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)

RanblogRan

If you haven't heard of this book and are interested in learning number theory, I strongly recommend it since it is very friendly for beginners. You can check out the book by this link:

Elementary Number Theory (Paperback)

Get it now:

Also, for my solutions, 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.1 (p. 43)

1. It has been conjectured that there are infinitely many primes of the form $n^{2} - 2$. Exhibit five such primes.
2. Give an example to show that the following conjecture is not true: Every positive integer can be written in the form $p + a^2$, where $p$ is either a prime or $1$, and $a \geq 0$.
3. Prove each of the assertions below:
   (a) Any prime of the form $3n + 1$ is also of the form $6m + 1$.
   (b) Each integer of the form $3n + 2$ has a prime factor of this form.
   (c) The only prime of the form $n^3 - 1$ is $7$.
   [Hint: Write $n^3 - 1$ as $(n - 1)(n^2 + n + 1)$.]
   (d) The only prime $p$ for which $3p + 1$ is a perfect square is $p = 5$.
   (e) The only prime of the form $n^2 - 4$ is $5$.
4. If $p \geq 5$ is a prime number, show that $p^2 + 2$ is composite. [Hint: $p$ takes one of the forms $6k + 1$ or $6k + 5$.]
5. (a) Given that $p$ is a prime and $p \mid a^n$, prove that $p^n \mid a^n$.
   (b) If $gcd(a, b) = p$, a prime, what are the possible values of $gcd(a^2 , b^2)$, $gcd(a^2 , b)$ and $gcd(a^3, b^2)$?
6. Establish each of the following statements:
   (a) Every integer of the form $n^4 + 4$, with $n \gt 1$, is composite.
   [Hint: Write $n^4 + 4$ as a product of two quadratic factors.]
   (b) If $n \gt 4$ is composite, then $n$ divides $(n - 1)!$.
   (c) Any integer of the form $8^n + 1$, where $n \geq 1$, is composite.
   [Hint: $2^n + 1 \mid 2^{3n} + 1$.]
   (d) Each integer $n > 11$ can be written as the sum of two composite numbers.
   [Hint: If $n$ is even, say $n = 2k$, then $n - 6 = 2(k - 3)$; for $n$ odd, consider the integer $n - 9$.]
7. Find all prime numbers that divide $50!$.
8. If $p \geq q \geq 5$ and $p$ and $q$ are both primes, prove that $24 \mid p^2 - q^2$.
9. (a) An unanswered question is whether there are infinitely many primes that are $1$ more than a power of $2$, such as $5 = 2^2 + 1$. Find two more of these primes.
   (b) A more general conjecture is that there exist infinitely many primes of the form $n^2 + 1$; for example, $257 = 162 + 1$. Exhibit five more primes of this type.
10. If $p \neq 5$ is an odd prime, prove that either $p^2 - 1$ or $p^2 + 1$ is divisible by $10$.
11. Another unproven conjecture is that there are an infinitude of primes that are $1$ less than a power of $2$, such as $3 = 2^2 - 1$.
    (a) Find four more of these primes.
    (b) If $p = 2^k - 1$ is prime, show that $k$ is an odd integer, except when $k = 2$. [Hint: $3 \mid 4^n - 1$ for all $n \geq 1$.]
12. Find the prime factorization of the integers $1234$, $10140$, and $36000$.
13. If $n \gt 1$ is an integer not of the form $6k + 3$, prove that $n^2 + 2^n$ is composite. [Hint: Show that either $2$ or $3$ divides $n^2 + 2^n$ .]
14. It has been conjectured that every even integer can be written as the difference of two consecutive primes in infinitely many ways. For example, $$6 = 29 - 23 = 137 - 131 = 599 - 593 = 1019 - 1013 = ...$$
    Express the integer 10 as the difference of two consecutive primes in 15 ways.
15. Prove that a positive integer $a \gt 1$ is a square if and only if in the canonical form of a all the exponents of the primes are even integers.
16. An integer is said to be square-free if it is not divisible by the square of any integer greater than $1$. Prove the following:
    (a) An integer $n > 1$ is square-free if and only if n can be factored into a product of distinct primes.
    (b) Every integer $n > 1$ is the product of a square-free integer and a perfect square.
    [Hint: If $n = {p_{1}}^{k_{1}}{p_{2}}^{k_{2}} \cdots {p_{s}}^{k_{s}}$ is the canonical factorization of $n$, then write $k_{i} = 2q_{i} + r_{i}$ where $r_{i} = 0$ or $1$ according as $k_{i}$ is even or odd.]
17. Verify that any integer $n$ can be expressed as $n = 2^{k}m$, where $k \geq 0$ and $m$ is an odd integer.
18. Numerical evidence makes it plausible that there are infinitely many primes $p$ such that $p + 50$ is also prime. List $15$ of these primes.
19. A positive integer $n$ is called square-full, or powerful, if $p^{2} \mid n$ for every prime factor $p$ of $n$ (there are $992$ square-full numbers less than $250,000$). If $n$ is square-full, show that it can be written in the form $n = a^{2}b^{3}$, with $a$ and $b$ positive integers.

My Solutions (Q1 - Q19)

Q1

It has been conjectured that there are infinitely many primes of the form $n^{2} - 2$. Exhibit five such primes.

Solution:

When $n = 2$, $2^2 - 2 = 4 - 2 = 2$.
When $n = 3$, $3^2 - 2 = 9 - 2 = 7$.
When $n = 5$, $5^2 - 2 = 25 - 2 = 23$.
When $n = 7$, $7^2 - 2 = 49 - 2 = 47$.
When $n = 9$, $9^2 - 2 = 81 - 2 = 79$.

All of these are primes.

Q2

Give an example to show that the following conjecture is not true: Every positive integer can be written in the form $p + a^2$, where $p$ is either a prime or $1$, and $a \geq 0$.

Solution:

We can check the positive integers starting from $1$. Then we will find that $25$ is the counterexample.

When $a = 0$, 25 = $0^2 + 25$ where $25$ is not a prime.
When $a = 1$, 25 = $1^2 + 24$ where $24$ is not a prime.
When $a = 2$, 25 = $2^2 + 21$ where $21$ is not a prime.
When $a = 3$, 25 = $3^2 + 16$ where $16$ is not a prime.
When $a = 4$, 25 = $4^2 + 9$ where $9$ is not a prime.
When $a = 5$, 25 = $5^2 + 0$ where $0$ is not a prime.

Q3

Prove each of the assertions below:

(a) Any prime of the form $3n + 1$ is also of the form $6m + 1$.
(b) Each integer of the form $3n + 2$ has a prime factor of this form.
(c) The only prime of the form $n^3 - 1$ is $7$.
[Hint: Write $n^3 - 1$ as $(n - 1)(n^2 + n + 1)$.]
(d) The only prime $p$ for which $3p + 1$ is a perfect square is $p = 5$.
(e) The only prime of the form $n^2 - 4$ is $5$.

Solution:

(a)

If $3n + 1$ is prime for some integer $n$ where $n \geq 1$, it must be an odd integer. Therefore, $n$ must be an even integer. Otherwise, $3n + 1$ will become even.

Therefore, $n$ is in the form of $2k$ for some integer $k$ where $k \geq 0$. $3n + 1 = 3(2k) + 1 = 6k + 1$ which is in the form of $6m + 1$ for some integer $m$.

(b)

By Theorem 2.1 Division Algorithm, the prime factors of $3n + 2$ are either of the forms $3k$, $3k + 1$, or $3k + 2$ for some integer $k$.

For $3k$, the only possible prime is $3$. But it is impossible because $3 \not \mid 3n + 2$. Hence, the only possible form is either $3k + 1$ or $3k + 2$.

We want to prove by contradiction. Let us assume that there are no prime factors of $3n + 2$ in the form of $3k + 2$. It means that $3n + 2 = (3k_{1} + 1)(3k_{2} + 1)...(3k_{m} + 1)$ for some integer $m$ where $m \geq 1$.

As we proved in Section 2.2 Q3(a), the square of $3k + 1$ is still in the same form, which means $(3k_{1} + 1)(3k_{2} + 1)...(3k_{m} + 1)$ will still be in the form of $3x + 1$ for some integer $x$. It contradicts the form $3n + 2$.

Therefore, there must exist a prime factor of $3n + 2$ in the same form.

(c)

If $n^3 - 1$ is a prime, by Definition 3.1, the only positive divisors are $1$ and $n^3 - 1$. As $n^3 - 1 = (n - 1)(n^2 + n + 1)$, we only have two situations to consider:

If $n - 1 = 1$, then $n = 2$.

If $n^2 + n + 1 = 1$, then $n = 0$ or $n = -1$ which is impossible. Because $n^3 - 1 = -1$ or $-2$, but prime must be greater than $1$ by the Definition 3.1.

Therefore, $n^3 - 1 = 2^3 - 1 = 7$.

(d)

If $3p + 1 = n^2$ for some integer $n$, we know $3p = n^2 - 1 = (n + 1)(n - 1)$. By the Theorem 3.2 Fundamental Theorem of Arithmetic, we know either $n + 1 = 3$ or $n - 1 = 3$. Thus $n = 2$ or $n = 4$.

If $n = 2$, $p = 1$, which is not a prime.
If $n = 4$, $p = 5$ which is the only prime.

(If it feels unobvious to you when I say "either $n + 1 = 3$ or $n - 1 = 3$", you may be thinking not both $n + 1$ and $n - 1$ are primes. Then try to consider this, if $n + 1$ or $n - 1$ is composite, then it will be broken down to more than 2 prime factors, which contradicts with uniqueness stated in the Fundamental Theorem of Arithmetics because $3p$ are only two prime factors.)

(e)

We know $n^2 - 4 = (n + 2)(n - 2)$. If $n^2 - 4$ is a prime, we know either $n + 2 = 1$ or $n - 2 = 1$. Thus $n = -1$ or $n = 3$.

If $n = -1$, $n^2 - 4 = -3$, which is not a prime.
If $n = 3$, $n^2 - 4 = 5$, which is the only prime.

Q4

If $p \geq 5$ is a prime number, show that $p^2 + 2$ is composite. [Hint: $p$ takes one of the forms $6k + 1$ or $6k + 5$.]

Solution:

By Theorem 2.1 Division Algorithm, we can write $p$ in the form of $6k$, $6k + 1$, ... and $6k + 5$ for some integer $k$. We know $p$ only takes the form $6k + 1$ and $6k + 5$ since all other forms are composites.

For $6k + 1$:

which is divisible by $3$.

As $p \geq 5$, $p^2 + 2 \geq 27$. Thus $12k^2 + 4k + 1 \neq 1$. So $p^2 + 2$ is a composite in this case.

For $6k + 5$:

which is divisible by $3$.

Similarly, $12k^2 + 20k + 9 \neq 1$. So $p^2 + 2$ is also a composite in this case.

Therefore, if $p \geq 5$ is a prime number, $p^2 + 2$ is composite.

Q5

(a) Given that $p$ is a prime and $p \mid a^n$, prove that $p^n \mid a^n$.
(b) If $gcd(a, b) = p$, a prime, what are the possible values of $gcd(a^2 , b^2)$, $gcd(a^2 , b)$ and $gcd(a^3, b^2)$?

Solution:

(a)

By Corollary 2 of Theorem 3.2, $p \mid a^n$ implies that $p \mid a$. So, $a = pk$ for some integer $k$. Thus $a^n = p^{n}k^{n}$, which means $p^n \mid a^n$.

(b)

Because $gcd(a, b) = p$, we know $p \mid a$ and $p \mid b$. So, $p \mid a^2$ and $p \mid b^2$. Using (a), we have $p^2 \mid a^2$ and $p^2 \mid b^2$.

Therefore, the possible values for $gcd(a^2 , b^2)$, $gcd(a^2 , b)$, and $gcd(a^3, b^2)$ are $p^2$, $p$, and $p^2$ respectively.

Q6

Establish each of the following statements:
(a) Every integer of the form $n^4 + 4$, with $n \gt 1$, is composite.
[Hint: Write $n^4 + 4$ as a product of two quadratic factors.]
(b) If $n \gt 4$ is composite, then $n$ divides $(n - 1)!$.
(c) Any integer of the form $8^n + 1$, where $n \geq 1$, is composite.
[Hint: $2^n + 1 \mid 2^{3n} + 1$.]
(d) Each integer $n > 11$ can be written as the sum of two composite numbers.
[Hint: If $n$ is even, say $n = 2k$, then $n - 6 = 2(k - 3)$; for $n$ odd, consider the integer $n - 9$.]

Solution:

(a)

As $n \gt 1$, $n^2 + 2 + 2n \gt 5$ and $n^2 + 2 - 2n \gt 1$. Thus $n^4 + 4$ has two positive divisors other than $1$ and $n^4 + 4$. Therefore, every integer form of $n^4 + 4$ is a composite.

(b)

As $n$ is composite, $n = ab$ for integers $a$, $b$ where $1 \lt a, b \lt n$. There are only two cases:

If $a \neq b$, $a$ and $b$ will both appear in $(n - 1)!$. Then $n \mid (n - 1)!$.

If $a = b$, we have $n = a^2$. Since $n = a^2 \gt 4$ and $a \gt 1$, we know $a \gt 2$. Thus we multiply both sides by $a$ to get $a^2 \gt 2a$, which means $2a$ is also in $(n - 1)!$. Therefore, $(2a)(a) = 2a^2 = 2n \mid (n - 1)!$ which means that $n \mid (n - 1)!$.

(c)

Let $x = 2^n$. By using the hint, we know $x + 1 \mid x^3 + 1$. By long division or if you remember the formula that $x^3 + 1 = (x + 1)(x^2 - x + 1)$, we have $8^n + 1 = (2^n + 1)(4^n - 2^n + 1)$.

As $n \geq 1$, we know $2^n + 1 \geq 3$ and $4^n - 2^n + 1 \geq 3$. Therefore, any integer of the form $8^n + 1$, where $n \geq 1$, is composite.

(d)

If $n$ is even, we have $n = 2k$ for some integer $k$. Then $n - 6 = 2(k - 3)$. Thus $n = 6 + 2(k-3)$.

If $n$ odd, we have $n = 2k + 1$ for some integer $k$. Then $n - 9 = 2k + 1 - 9 = 2(k-4)$. Thus $n = 9 + 2(k - 4)$.

Q7

Find all prime numbers that divide $50!$.

Solution:

First, all prime numbers that are $\lt 50$ can divide $50!$ because they are terms in $50!$. These prime numbers are $2$, $3$, $5$, $7$, $11$, $13$, $17$, $19$, $23$, $29$, $31$, $37$, $41$, $43$, and $47$.

By Theorem 3.2 fundamental theorem of arithmetic, all the non-prime terms in $50!$ have unique representations in a product of primes. The primes should be less than the term which will also be less than $50$.

Therefore, all prime numbers that divide $50!$ are the numbers listed above.

Q8

If $p \geq q \geq 5$ and $p$ and $q$ are both primes, prove that $24 \mid p^2 - q^2$.

Solution:

By Theorem 2.1 Division Algorithm, we can write $p = 2k + 1$ and $q = 2m + 1$ for some integers $k$ and $m$.

We know the product of $2$ consecutive integers is divisible by $2$. Thus we can factor out the $2$ from $k(k + 1)$ and $m(m + 1)$. So, $8 \mid p^2 - q^2$.

We also want to prove $3 \mid p^2 - q^2$.

By Theorem 2.1 Division Algorithm, we can write $p = 3k + r$ and $q = 3m + s$ for some integers $k$ and $m$, where $r$ and $s$ can only equal to $1$ or $2$ as $p$ and $q$ are primes.

Now we only need to check whether $3 \mid r^2 - s^2$ or not. We know $r^2 - s^2 = (r + s)(r - s)$. If $r \neq s$, $r + s = 3$. If $r = s$, $r - s = 0$. Therefore, $3 \mid r^2 - s^2$. Thus $3 \mid p^2 - q^2$.

Because $gcd(8, 3) = 1$, we know $24 \mid p^2 - q^2$ by using corollary 2 of Theorem 2.4.

Q9

(a) An unanswered question is whether there are infinitely many primes that are $1$ more than a power of $2$, such as $5 = 2^2 + 1$. Find two more of these primes.
(b) A more general conjecture is that there exist infinitely many primes of the form $n^2 + 1$; for example, $257 = 162 + 1$. Exhibit five more primes of this type.

Solution:

(a)

$2^4 + 1 = 17$ and $2^8 + 1 = 257$.

(b)

$4^2 + 1 = 17$, $6^2 + 1 = 37$, $10^2 + 1 = 101$, $14^2 + 1 = 197$, and $20^2 + 1 = 401$.

Q10

If $p \neq 5$ is an odd prime, prove that either $p^2 - 1$ or $p^2 + 1$ is divisible by $10$.

Solution:

Because $p \neq 5$ and $p$ is a prime, $5 \not \mid p$. By Theorem 2.1 Division Algorithm, we can write $p$ in the form of $10k + 1$, $10k + 3$, $10k + 7$ or $10k + 9$.

When $p = 10k + 1$, $p^2 = (10k + 1)^2 = 100k^2 + 20k + 1$. $10 \mid p^2 - 1$.
When $p = 10k + 3$, $p^2 = (10k + 3)^2 = 100k^2 + 60k + 9$. $10 \mid p^2 + 1$.
When $p = 10k + 7$, $p^2 = (10k + 7)^2 = 100k^2 + 140k + 49$. $10 \mid p^2 + 1$.
When $p = 10k + 9$, $p^2 = (10k + 9)^2 = 100k^2 + 180k + 81$. $10 \mid p^2 - 1$.