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:

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

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$.

$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$.

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$.

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.

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

Related Pages

< Chapter 3.3, Q4 Chapter 3.3, Q6 >