Chapter 1 What is number theory

Number theory is the study of the set of positive whole numbers, which is often called the set of natural numbers.

We know natural numbers have different types: odd, even, square, cube, prime ( 质数 ), composite ( 合数 ), x mod y, triangular, perfect, fibonacci.

The main goal of number theory is to discover interesting and unexpected relationships between different sorts of numbers and to prove that these relatinships are true.

If we want to study math, number theory is partly experimental and partly theoretical. ( 数论一半是实验性的，一半是理论性的 ):

• Accumulate data, usually numerical, but sometimes more abstract in nature.
• Examine the data and try to find patterns and relationships.
• Formulate conjectures (i.e., guesses) that explain the patterns and relationships. These are frequently given by formulas.
• Test your conjectures by collecting additional data and checking whether the new information fits your conjectures.
• Devise an argument (i.e., a proof) that your conjectures are correct.

这一节主要是介绍了数论是研究自然数之间的关系，如果我们想研究各种关系的情况，需要通过大量的收集数据，观察数据之间的关系和规律，后续提出猜想，来用大量的数据来验证猜想是否正确，后续需要证明你的猜想是正确的.

1.1 The first two numbers that are both squares and triangles are 1 and 36. Find the next one and, if possible, the one after that. Can you figure out an efficient way to find triangular-square numbers? Do you think that there are infinitely many?

I found some numbers using code.

for i in range(1, 10000):
    triangles_number = i * (i + 1) // 2
    square_root = int(triangles_number ** 0.5)
    if square_root * square_root == triangles_number:
        print(f"Triangular-square number found: {triangles_number} (Triangle index: {i}, Square root: {square_root})")

result:
- 1 (Triangle index: 1, Square root: 1)
- 36 (Triangle index: 8, Square root: 6)
- 1225 (Triangle index: 49, Square root: 35)
- 41616 (Triangle index: 288, Square root: 204)
- 1413721 (Triangle index: 1681, Square root: 1189)
- 48024900 (Triangle index: 9800, Square root: 6930)

i find patterns and relationships about these data:

Square root : $6 \times 6 - 1 = 35, 6 \times 35 - 6 = 204, 6 \times 204 - 35 = 1189$ … $m_{k+1} = 6m_k - m_{k-1}$

Triangle index: $6 \times 8 - 1 + 2 = 49, 6 \times 49 - 8 + 2 = 288, 6 \times 288 - 49 + 2 = 1681$ … $m_{k+1} = 6m_k - m_{k-1} + 2$

I want to prove this formula：

$\frac {(1 + n) \times n} {2} = m ^ 2$

$4n ^ 2 + 4n = 8m^2$

$(2n + 1)^2 - 8m^2 = 1$

if $ x = 2n + 1 $ and $ y = 2m$

we can get $ x^2 - 2y^2 = 1$ because Pell’s equation is $x^2 - Dy^2 = 1$

If n and m are 0, it doesn’t make any sense. $x=3, y=2$ is the smallest nontrivial solution

$(3 + 2\sqrt 2)(3 - 2\sqrt 2) = 1$

$(x + y\sqrt 2)(x - y\sqrt 2) = 1$

$(3 + 2\sqrt 2)(3 - 2\sqrt 2)(x + y\sqrt 2)(x - y\sqrt 2) = 1$

$(3x + 4y + \sqrt 2(2x + 3y))(3x + 4y - \sqrt 2(2x + 3y)) = 1$

if $3x + 4y = x'$ and $2x + 3y = y'$

we can get $(x' + \sqrt 2 y')(x' - \sqrt 2 y') = 1$ $x'^2 - 2y'^2 =1$

Therefore there are infinitely many solutions. For example, starting from the solution $(x, y) = (3, 2)$, the formulas $x' = 3x + 4y$ and $y' = 2x + 3y$ give a new solution $(17, 12)$. Since $x = 2n + 1$ and $y = 2m$, this new solution gives $n = 8$ and $m = 6$, which is the square–triangular number $36$. Each time we apply the formulas, we get a strictly larger solution, so this process never stops. Therefore there are infinitely many square–triangular numbers.

1.2 Try adding up the first few odd numbers and see if the numbers you get satisfy some sort of pattern. Once you find the pattern, express it as a formula. Give a geometric verification that your formula is correct.

I adding up the first few odd numbers:

the sums are exactly the square numbers, Let $x$ be the last odd number in the sum. Then the number of terms is $\frac{x+1}{2}$, so

If the sum does not start from 1 but from some odd number $a$, we can subtract the missing part. Let $m = a - 2$ be the odd number just before $a$. Then

Geometric verification. Arrange $n^2$ dots in an $n \times n$ square, and cut the square into L-shaped layers. Consider the layer whose side length is $s = \frac{x-1}{2} + 1$, where $x$ is an odd number. This layer contains

1.3 The consecutive odd numbers 3, 5, and 7 are all primes. Are there infinitely many such “prime triplets”? That is, are there infinitely many prime numbers p such that p + 2 and p + 4 are also primes?

The odd multiples of 3 are $9, 15, 21, 27, \ldots$, appearing every 6. We show that every triple $(p,\ p+2,\ p+4)$ with $p > 3$ contains one of them.

Starting from $p = 5$ and moving forward by 6 each time, the triples

each contain a multiple of 3 in the third position ($p + 4$).

Suppose the first position skips past the multiple of 3 and starts at the very next odd number. Then the new third position is $(p + 4) + 2 + 4 = (p + 4) + 6$. Since $(p+4) \bmod 3 \equiv 0$, adding 6 does not change the remainder, so $((p+4) + 6) \pmod 3 \equiv 0 $ as well. The new triple therefore contains a multiple of 3 again. It follows that there are not infinitely many primes $p$ such that $p + 2$ and $p + 4$ are also primes.

1.4. It is generally believed that infinitely many primes have the form N2 + 1, although no one knows for sure. (a) Do you think that there are infinitely many primes of the form $N^2 - 1$? (b) Do you think that there are infinitely many primes of the form $N^2 - 2$? (c) How about of the form $N^2 - 3$? How about $N^2 - 4$? (d) Which values of a do you think give infinitely many primes of the form $N^2 - a$

If a is not a perfect square can have infinitely many primes.

For example, $N^2 - 1 = (N+1)(N-1)$, so this number always has at least two known factors, namely $N+1$ and $N-1$.

If $a$ is a square number, say $a = k^2$, then by the difference of two squares formula, $N^2 - a = (N+k)(N-k)$.

1.5. The following two lines indicate another way to derive the formula for the sum of the first $n$ integers by rearranging the terms in the sum. Fill in the details. $$1 + 2 + 3 + \cdots + n = (1 + n) + (2 + (n-1)) + (3 + (n-2)) + \cdots$$ $$= (1 + n) + (1 + n) + (1 + n) + \cdots$$How many copies of $n + 1$ are in there in the second line? You may need to consider the cases of odd $n$ and even $n$ separately. If that’s not clear, first try writing it out explicitly for $n = 6$ and $n = 7$.

Instead of treating the two cases separately, I derived a single formula that covers both:

1.6. For each of the following statements, fill in the blank with an easy-to-check criterion: (a) $M$ is a triangular number if and only if ____ is an odd square. (b) $N$ is an odd square if and only if ____ is a triangular number. (c) Prove that your criteria in (a) and (b) are correct.

Chapter 2 Pythagorean Triples

学习这一章节的时候，发现一句话写的很好： Our goal in this book is to understand and appreciate some truly beautiful mathematics, to learn how this mathematics was discovered and proved, and maybe even to make some original contributions of our own.

A primitive Pythagorean triple (PPT) is a triple of numbers(a, b, c) such that a, b, and c have no common factors and satisfy $a^2 + b^2 = c^2$

Why study the primitive Pythagorean triple? Because every right-angled triangle is derived from this primitive triangle by multiplying it by a scaling factor.

Let $(a, b, c)$ be a PPT. We show that exactly one of $a$ and $b$ is odd, and that $c$ is odd.

$a$ and $b$ cannot both be even. If they were, then $c^2 = a^2 + b^2$ would be even. The square of an odd number is odd, so $c$ would be even too. Then $2$ would be a common factor of $a$, $b$, $c$, and the triple would not be primitive.

$a$ and $b$ cannot both be odd. Suppose they were. Then $c^2 = a^2 + b^2$ is odd + odd = even, so $c$ is even. Write

Substituting into $a^2 + b^2 = c^2$ gives

so if a b are both odd and c is even not right.

$d$ divides both $c - b$ and $c + b$. Then $d$ also divides their sum and their difference:

So $d$ divides both $2b$ and $2c$. But $b$ and $c$ have no common factor, because $(a, b, c)$ is primitive. (If a prime $p$ divided both $b$ and $c$, then $p$ would divide $c^2 - b^2 = a^2$, and hence $a$, by the prime property in Step 5. Then $p$ would be a common factor of $a$, $b$, $c$.) Hence $d$ is $1$ or $2$.

On the other hand, $d$ divides $(c - b)(c + b) = a^2$, and $a^2$ is odd because $a$ is odd. So $d \neq 2$, and therefore $d = 1$

$c - b$ and $c + b$ are positive integers with no common factor, and their product is the square $a^2$. The only way this can happen is if $c - b$ and $c + b$ are themselves squares.

we can write

where:

• $s > t \geq 1$, because $c + b > c - b \geq 1$. (Note that $c > b$, since $c^2 = a^2 + b^2 > b^2$.)
• $s$ and $t$ are odd, because $c + b$ and $c - b$ are odd (odd $\pm$ even).
• $s$ and $t$ have no common factor, because a common factor of $s$ and $t$ would also divide $s^2 = c + b$ and $t^2 = c - b$.

Adding and subtracting the two equations, we solve for $c$ and $b$:

and then

We will get every primitive Pythagorean triple $(a, b, c)$ with $a$ odd and $b$ even by using the formulas

First, $a$, $b$, $c$ are natural numbers. Since $s$ and $t$ are odd, $s^2$ and $t^2$ are odd, so $s^2 + t^2$ and $s^2 - t^2$ are even, and $b$, $c$ are integers. Since $s > t$, we have $b > 0$.

Then a little algebra shows that $a^2 + b^2 = c^2$:

If $s > t \geq 1$ are odd integers with no common factors, then $a = st$, $b = \frac{s^2 - t^2}{2}$, $c = \frac{s^2 + t^2}{2}$ have no common factors.

It is enough to show that $b$ and $c$ have no common factor, because any common factor of $a$, $b$, $c$ is also a common factor of $b$ and $c$.

Suppose, for contradiction, that a prime $p$ divides both $b$ and $c$. (It is enough to look at primes: any common factor greater than 1 has a prime factor, and that prime also divides both $b$ and $c$.) Then $p$ divides their sum and their difference:

If a prime $p$ divides both $s^2$ and $t^2$, then $p$ must divide both $s$ and $t$. But by assumption, $s$ and $t$ have no common factors, so no such $p$ exists. Therefore $a$, $b$, $c$ have no common factors.

So the formulas produce exactly the primitive Pythagorean triples with $a$ odd and $b$ even.