Elementary Number Theory Problems 3.3 Solution (David M. Burton's 7th Edition) - Q5
Background
All theorems, corollaries, and definitions listed in the book's order:
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
In 1752, Goldbach submitted the following conjecture to Euler: Every odd integer can be written in the form $p + 2a^2$, where $p$ is either a prime or $1$ and $a \geq 0$. Show that the integer $5777$ refutes this conjecture.
Solution
If $p$ is $1$, then $5777 = 1 + 2a^2$.
$$ \begin{equation} \begin{split} 5777 & = 1 + 2a^2 \\ 5776 & = 2a^2 \\ 2888 & = a^2 \\ \end{split} \nonumber \end{equation} $$$a \approx 53.74$, which is not an integer.
If $p$ is a prime, we have $5777 - 2a^2 = p$.
The simplest method is checking $a = 1, 2, 3, ...$ to see whether all $5777 - 2a^2$ equals any prime. As the smallest prime is $2$, the largest $a$ would be $\sqrt{\frac{5777 - 2}{2}} = \sqrt{2887.5} \approx 53.74$. Thus, the range for $a$ would be $0 \leq a \leq 53$.
In order to have fewer calculations, let us consider the remainder of $5777 - 2a^2$ divided by $3$.
By Theorem 2.1 Division Algorithm, we can write $a = 3k, 3k +1$, and $3k + 2$ for some integer $k$.
$$ \begin{equation} \begin{split} p & = 5777 - 2a^2 & \\ & = 3 \times 1925 + 2 - 2a^2 \\ & = \begin{cases} 3q & \text{if $a = 3k + 1$ or $a = 3k + 2$} \\ 3q + 2 & \text{if $a = 3k$} \end{cases} \end{split} \nonumber \end{equation} $$for some integer $q$.
In the first case, it means $3 \mid p$. The only possible $p$ is $3$, but there is no such integer $a$. Thus, we only need to consider the second case. It means that we should only check the $a$ where $3 \mid a$.
This leaves us only $17$ choices to check in the range $0 \leq a \leq 53$, which is ${3, 6, 9, ..., 51}$.
Similarly, by Theorem 2.1 Division Algorithm, we can write $a = 5m, 5m +1$, $5m + 2$, $5m + 3$, and $5m + 4$ for some integer $m$.
$$ \begin{equation} \begin{split} p & = 5777 - 2a^2 & \\ & = 5 \times 1155 + 2 - 2a^2 \\ & = \begin{cases} 5n & \text{if $a = 5m + 1$ or $a = 5m + 4$} \\ 5n + 2 & \text{if $a = 5m$} \\ 5n + 4 & \text{if $a = 5m + 2$ or $5m + 3$} \end{cases} \end{split} \nonumber \end{equation} $$for some integer $n$.
In the first case, it means $5 \mid p$. The only possible prime $p$ is $5$, but there is no such integer $a$. Thus, we only need to consider the second case and the third case. It means that we can eliminate choices when $a = 5m + 1$ or $a = 5m + 4$.
Therefore, we can further eliminate choices from the set $\{3, \bcancel{6}, \bcancel{9}, 12, 15, 18, \bcancel{21}, \bcancel{24}, 27, 30, 33, \bcancel{36}, \bcancel{39}, 42, 45, 48, \bcancel{51}\}$. This leaves the range for $a$ as $\{3, 12, 15, 18, 27, 30, 33, 42, 45, 48 \}$.
If $a = 3$, $p = 5777 - 2a^2 = 5759$, having $13$ as a factor, so $p$ is not a prime.
If $a = 12$, $p = 5777 - 2a^2 = 5489$, having $11$ as a factor, so $p$ is not a prime.
If $a = 15$, $p = 5777 - 2a^2 = 5327$, having $7$ as a factor, so $p$ is not a prime.
If $a = 18$, $p = 5777 - 2a^2 = 5129$, having $23$ as a factor, so $p$ is not a prime.
If $a = 27$, $p = 5777 - 2a^2 = 4319$, having $7$ as a factor, so $p$ is not a prime.
If $a = 30$, $p = 5777 - 2a^2 = 3977$, having $41$ as a factor, so $p$ is not a prime.
If $a = 33$, $p = 5777 - 2a^2 = 3599$, having $59$ as a factor, so $p$ is not a prime.
If $a = 42$, $p = 5777 - 2a^2 = 2249$, having $13$ as a factor, so $p$ is not a prime.
If $a = 45$, $p = 5777 - 2a^2 = 1727$, having $11$ as a factor, so $p$ is not a prime.
If $a = 48$, $p = 5777 - 2a^2 = 1169$, having $7$ as a factor, so $p$ is not a prime.
Therefore, integer $5777$ refutes this conjecture.
Alternative approach if not considering "$5777 - 2a^2$ divided by $5$":
In order to eliminate more situations, let us consider the last digit of $5777 - 2a^2$. For that, we need to consider the last digit of $a$, $a^2$, and $2a^2$ first.
| $a$ | $a^2$ | $2a^2$ | $5777 - 2a^2$ |
|---|---|---|---|
| 0 | 0 | 0 | 7 |
| 1 | 1 | 2 | 5 |
| 2 | 4 | 8 | 9 |
| 3 | 9 | 8 | 9 |
| 4 | 6 | 2 | 5 |
| 5 | 5 | 0 | 7 |
| 6 | 6 | 2 | 5 |
| 7 | 9 | 8 | 9 |
| 8 | 4 | 8 | 9 |
| 9 | 1 | 2 | 5 |
The only possible last digit for $2a^2$ are $0$, $2$, and $8$. Thus, the last digit of $5777 - 2a^2$ will be $7$, $5$, and $9$. If the last digit of $5777 - 2a^2$ is $5$, the only possible prime $p$ will be $5$ as all numbers with the last digit being $5$ have $5$ as a factor.
But $5$ is impossible as $a = \sqrt{\frac{5777 - 5}{2}}$ is not an integer. Therefore, if the last digit of $a$ is $1$, $4$, $6$, or $9$, we can eliminate them as the last digit of $5777 - 2a^2$ will be $5$. Therefore, we can further eliminate choices from the set $\{3, \bcancel{6}, \bcancel{9}, 12, 15, 18, \bcancel{21}, \bcancel{24}, 27, 30, 33, \bcancel{36}, \bcancel{39}, 42, 45, 48, \bcancel{51}\}$. This leaves the range for $a$ as $\{3, 12, 15, 18, 27, 30, 33, 42, 45, 48 \}$.
If $a = 3$, $p = 5777 - 2a^2 = 5759$, having $13$ as a factor, so $p$ is not a prime.
If $a = 12$, $p = 5777 - 2a^2 = 5489$, having $11$ as a factor, so $p$ is not a prime.
If $a = 15$, $p = 5777 - 2a^2 = 5327$, having $7$ as a factor, so $p$ is not a prime.
If $a = 18$, $p = 5777 - 2a^2 = 5129$, having $23$ as a factor, so $p$ is not a prime.
If $a = 27$, $p = 5777 - 2a^2 = 4319$, having $7$ as a factor, so $p$ is not a prime.
If $a = 30$, $p = 5777 - 2a^2 = 3977$, having $41$ as a factor, so $p$ is not a prime.
If $a = 33$, $p = 5777 - 2a^2 = 3599$, having $59$ as a factor, so $p$ is not a prime.
If $a = 42$, $p = 5777 - 2a^2 = 2249$, having $13$ as a factor, so $p$ is not a prime.
If $a = 45$, $p = 5777 - 2a^2 = 1727$, having $11$ as a factor, so $p$ is not a prime.
If $a = 48$, $p = 5777 - 2a^2 = 1169$, having $7$ as a factor, so $p$ is not a prime.
Therefore, integer $5777$ refutes this conjecture.
Why don't I use modular arithmetic?
Because this question appeared in Chapter 3, while modular arithmetic was introduced in Chapter 4 of the book.
Reference
The method is inspired by the discussion in PhysicsForums.
Read More: All My Solutions for This Book