# Notes on “A Friendly Introduction to Number Theory”

## Chap.1 What Is Number Theory?

Number Theory is the study of the set of positive whole numbers $1, 2, 3, 4, 5, 6, 7, …$, which are often called the set of natural numbers. We will especially want to strudy the relationship between different sorts of numbers.

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

Number Theory is partly experimental (comes first) and partly theoretical (follows).

Steps to follow:

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

## Chap.2 Pythagorean Triples

Why we study Pythagorean triples, or further more, Number Theory?

There is at least one good reason to study Pythagorean triples, and it’s the same reason why it is worthwhile studying the art of Rembrandt and the music of Beethoven. There is a beauty to the ways in which numbers intereact with one another, just as there is a beauty in the composition of a painting or a symphony. To appreciate this beauty, one has to be willing to expend a certain amount of mental energy. But the end result is well worth the effort. Our goal in this book is to understand and appreciate some truly beautiful mathematics, to learn how this mathematics was dicovered and proved, and maybe even to make some original contributions of our own.

A primitive Pythagorean triple (or PPT for short) 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.

Theorem 2.1 (Pythagoream Triples Theorem). We will get every primitive Pythagorean triple (a, b, c) with a odd and b even by using the formulas  a = st, b = (s^2 - t^2)/2, c = (s^2 + t^2)/2, where s > t >= 1 are chosen to be any odd integers with no common factors.

## Chap.3 Pythagorean Triples and the Unit Circle

Theorem 3.1. Every point on the circle x^2 + y^2 = 1 whose coordinates are rational numbers can be obtained from the formula (x, y) = ( (1-m^2)/(1+m^2), 2m/(1+m^2) ) by substituting in rational numbers for m [except for the point (-1, 0) which is the limiting value as m -> ∞].

## Chap.4 Sum of Higher Powers and Fermat’s Last Theorem

Fermat’s Last Theorem. The equation a^n + b^n = c^n has no solutions in positive integers if n >= 3.

… Finally, in 1994, Andrew Wiles completed the proof of Fermat’s 350-year-old claim.

## Chap.5 Divisibility and the Greatest Common Divisor

 1 2 3 4  def gcd(a, b): while b: a, b = b, a % b return a 

## Chap.6 Linear Equations and the Greatest Common Divisor

ax + by is divisible by gcd(a, b).

Conclusion: The smallest positive value of ax + by is equal to gcd(a, b).

Theorem 6.1 (Linear Equation Theorem). Let a and b be nonezero integers, and let g = gcd(a, b). The equation ax + by = g always has a solution (x1, y1) in integers, and this solution can be found by the Euclidean algorithm method described earlier. Then every solution to the equation can be obtained by substituting integers k into the formula (x1 + kb/g, y1 - ka/g).

 1 2 3 4 5 6 7 8 9  def egcd(a, b): u, u1 = 1, 0 v, v1 = 0, 1 while b: q, r = divmod(a, b) u, u1 = u1, u - q * u1 v, v1 = v1, v - q * v1 a, b = b, r return u, v, a 

## Chap.7 Factorization and the Fundamental Theorem of Arithmetic

Lemma 7.1. Let p be a prime number, and suppose that p divides the product ab. Then either p divides a or p divides b (or p divides both a and b).

Theorem 7.2 (Prime Divisibility Property). Let p be a prime number, and suppose that p divides the product a1a2...ar. Then p divides at least one of the facotors a1, a2, …, ar.

Theorem 7.3 (The Fundamental Theorem of Arithmetic). Every integer n >= 2 can be factored into a product of primes n = p1p2...pr in exactly one way.

Proof:

1. The number n can be factored into a product of primes in some way. (Induction, 即数学归纳法)
2. There is only one such factorization (aside from rearranging the factors). (Theorem 7.2)

## Chap8. Congruences

Theorem 8.1(Linear Congruence Theorem). Let a, c, and m be integers with m >= 1, and let g = gcd(a, m).

• If g ∤ c, then the congruence ax ≡ c (mod m) has no solutions.
• If g | c, then the congurence ax ≡ c (mod m) has exactly g incongruent solutions. To find the solutions,
1. first find a solution (u0, v0) to the linear equation au + mv = g.
2. Then x0 = cu0 / g is a solution to ax ≡ c (mod m), and a complete set of incongruent solutions is given by x ≡ x0 + km/g (mod m) for k = 0, 1, 2, ..., g-1.
  1 2 3 4 5 6 7 8 9 10  def linearCongruenceSolver(a, c, m): ''' Solve x such that a * x ≡ c (mod m) returns all the possible *x*s (mod m), None if no solution. ''' g = gcd(a, m) if c % g: return None u0 = egcd(a, m)[0] return [(c * u0 + k * m) // g % m for k in range(g)] 

Theorem 8.2 (Polynomial Roots Mod p Theorem). Let p be a prime number and let f(x) = a0x^d + a1x^(d-1) + ... + ad be a polynomial of degree d >= 1 with integer coefficients and p ∤ a0. Then the congruence f(x) ≡ 0 (mod p) has at most d incongruent solutions.

## Chap.9 Congruences, Powers, and Fermat’s little Theorem

Theorem 9.1 (Fermat’s Little Theorem). Let p be a prime number, and let a be any number with a ≢ 0 (mod p). Then a^(p-1) ≡ 1 (mod p).

Fermat’s Little Theorem can be used to show that a number is not a prime without actually factoring it.

Lemma 9.2. Let p be prime number and let a be a number with a ≢ 0 (mod p). Then the numbers a, 2a, 3a, ..., (p-1)a (mod p) are the same as the numbers 1, 2, 3, ..., (p-1) (mod p), although they may be in a different order.

## Chap.10 Congruences, Powers, and Euler’s Formula

Theorem 10.1 (Euler’s Formula). If gcd(a, m) = 1, then a^phi(m) ≡ 1 (mod m).

Lemma 10.2. If gcd(a, m) = 1, then the numbers are the same as the numbers b1, b2, b3, ..., bphi(m) (mod m), although they may be in a different order.

## Chap.11 Euler’s Phi Function and the Chinese Remainder Theorem

Theorem 11.1 (Phi Function Formulas). (a) If p is a prime and k >= 1, then phi(p^k) = p^k - p^(k-1). (b) If gcd(m, n) = 1, then phi(mn) = phi(m)phi(n).

Theorem 11.2 (Chinese Remainder Theorem). Let m and n be integers satisfying gcd(m, n) = 1, and let b and c be any integers. Then the simultaneous congruences x ≡ b (mod m) and x ≡ c (mod n) have exactly one solution with 0 <= x < mn.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24  # 适用于模数两两互质的情况，可以直接通过构造求解。 def CRT(ai, mi): # # make sure every two *m*s in *mi* are relatively prime # lcm = lambda x, y: x * y // gcd(x, y) # mul = lambda x, y: x * y # assert(reduce(mul, mi) == reduce(lcm, mi)) assert(isinstance(mi, list) and isinstance(ai, list)) M = reduce(lambda x, y: x * y, mi) ai_ti_Mi = [a * (M // m) * egcd(M // m, m)[0] for (m, a) in zip(mi, ai)] return reduce(lamdba x, y: x + y, ai_ti_Mi) % M # 推广，不要求模数两两互质，总体思路是代入合并，再解线性同余方程。 def GCRT(ai, mi): assert(isinstance(mi, list) and isinstance(ai, list)) a, m = ai[0], mi[0] for a1, m1 in zip(ai[1:], mi[1:]): # x ≡ a (mod m) ==> x = a + k * m # substitute in x ≡ a1 (mod m1) ==> k * m ≡ a1 - a (mod m1) k = linear_congruence_equation(m, a1 - a, m1) # solve k if not k: return None # The solution is x ≡ a + k * m (mod m * m1) a, m = a + k[0] * m, m * m1 return a 

## Chap.12 Prime Numbers

Prime numbers are the building blocks of number theory.

Theorem 12.1 (Infinitely Many Primes Theorem). There are infinitely many prime numbers.

Theorem 12.2 (Primes 3 (Mod 4) Theorem). There are infinitely many primes that are congruent to 3 modulo 4.

Theorem 12.3 (Dirichlet’s Theorem on Primes in Arithmetic Progressions). Let a and m be integers with gcd(a, m) = 1. Then there are infinitely many primes that are congruent to a modulo m. That is, there are infinitely many prime numbers p satisfying p ≡ a (mod m).

Theorem 12.2.是该定理的一个例子。该定理的证明颇为复杂，涉及到复分析。

## Chap.13 Counting Primes

How many primes are there?

Let π(x) = #{primes p with p<=x}.

Theorem 13.1 (The Prime Number Theorem). When x is large, the number of primes less than x is approximately equal to x / ln(x). In other words, lim x->∞ π(x) = x / ln(x).

There are many famous unsolved problems invovlling prime numbers.

Conjecture 13.2 (Goldbach’s Conjecture). Every even number n >= 4 is a sum of two primes.

In 1966, Chen Jing-run says that every(sufficiently large) even number is a sum of two numbers p + a, where p is a prime and a is either prime or a product of two primes.

Conjecture 13.3 (The Twin Primes Conjecture). There are infinitely many prime numbers p such that p + 2 is also prime.

Conjecture 13.4 (The N^2 + 1 Conjectur). There are infinitely many primes of the form N^2 + 1.

## Chap.14 Mersenne Primes

Proposition 14.1. If a^n - 1 is prime for some numbers a >= 2 and n >= 2, then a must equal 2 and n must be a prime.

## Chap.15 Mersenne Primes and Perfect Numbers

A perfect number is a number that is equal to the sum of its proper divisors.

Theorem 15.1 (Eucild’s Perfect Number Formula). If 2^p - 1 is a prime number, then 2^(p-1) * (2^p - 1) is a perfect.

Sigma Function: σ(n) = sum of all divisors of n (including 1 and n).

Theorem 15.3 (Sigma Function Formulas). (a) If p is a prime and k >= 1, then σ(p^k) = 1 + p + p^2 + ... + p^k = (p^(k+1) - 1) / (p - 1). (b) If gcd(m, n) = 1, then σ(mn) = σ(m)σ(n).

Theorem 15.4 (Euler’s Perfect Number Theorem). If n is an even perfect number, then n looks like n = 2^(p-1) * (2^p - 1), where 2^p - 1 is a Mersenne prime.

## Chap.16 Powers Modulo m and Successive Squaring

  1 2 3 4 5 6 7 8 9 10 11  def FastExponentiation(x, y, n): ''' Square-and-Mutiply for Modular Exponentiation. ''' b = bin(y)[2:] res = x for i in b[1:]: res = res * res % n if int(i): res = res * x % n return res 

## Chap.17 Computing kth Roots Modolu m

Algorithm 17.1 (How to Compute kth Roots Modulo m). Let b, k, and m be given integers that satisfy gcd(b, m) = 1 and gcd(k, phi(m)) = 1. The following steps give a solution to the congruence x^k ≡ b (mod m).

1. Compute phi(m).
2. Find positive integers d such that k * d ≡ 1 (mod phi(m)).
3. Then the solution is x ≡ b^d (mod m).

## Chap.19 Primality Testing and Carmichael Numbers

How can we tell if a (large) number is prime?

Theorem 19.3 (Rabin-Miller Test for Composite Numbers). Let n be an odd interger and write n - 1 = 2^k * q with q odd. If both of the following conditions are true for some a not divisible by n, then n is a composite number. (a) a^q ≡/ 1 (mod n). (b) a^(2^i *q) ≡/ -1 (mod n) for all i = 0, 1, ..., k - 1.

If n is an odd composite number, then at least 75% of the numbers a between 1 and n - 1 act as Rabin-Miller witnesses for n.

## Chap.20 Squares Modulo p

A nonzero number that is congruent to a square modulo p is called a quadratic residue modulo p (QR). A number that is not congruent to a square modulo p is called a (quadratic) nonresidue modulo p (NR). 平方剩余和平方非剩余的定义。

Theorem 20.1. Let p be an odd prime. Then there are exactly $\frac{p-1}{2}$ quadratic residues modulo p and exactly $\frac{p-1}{2}$ nonresidues modulo p. 平方剩余和平方非剩余的个数。

Theorem 20.2 (Quadratic Residue Multiplication Rule). (Version 1) Let $p$ be an odd prime. Then: (i) The product of two quadratic residues modulo $p$ is a quadratic residue. (ii) The product of a quadratic residue and a nonresidue is a nonresidue. (iii) The product of two nonresidues is a quadratic residue. $Q!R × Q!R = Q!R, Q!R × N!R = N!R, N!R × N!R = Q!R.$

Analogue to $1 ^ 1 = 0,\ 1 ^ 0 = 1,\ 0 ^ 0 = 0$, $+!1 × +!1 = +!1,\ +!1 × (-!1) = -!1,\ (-!1) × (-!1) = +!1$.异性相吸？

The Legendre symbol of a modulo p is:

$$(\frac{a}{p}) = \begin{cases} 1\quad if\ a\ is\ quadratic\ residue\ modulo\ p, \newline -1\quad if\ a\ is\ nonresidue\ modulo\ p. \end{cases}$$

Theorem 20.3 (Quadratic Residue Multiplication Rule). (Version 2) Let p be an odd prime. Then

$$(\frac{a}{p})(\frac{b}{p}) = (\frac{ab}{p}).$$

## Chap.21 Is -1 a Square Modulo p? Is 2?

For which primes p is -1 a QR?

Theorem 21.1 (Euler’s Criterion). Let p be an odd prime. Then

$$a^{\frac{p-1}{2}} ≡ (\frac{a}{p})\ (mod\ p).$$

Theorem 21.2 (Quadratic Reciprocity). (Part I) Let p be an odd prime. Then -1 is a quadratic residue modulo $p$, if $p \equiv 1\ (mod\ 4)$, and -1 is a nonresidue modulo $p$, if $p \equiv 3\ (mod\ 4)$.

$$(\frac{-1}{p}) = \begin{cases} 1\quad if\ p \equiv 1 \ (mod\ 4), \newline -1\quad if\ p \equiv 3 \ (mod\ 4). \end{cases}$$

-1QR还是NR？这个取决于质数p，若 $p \equiv 1\ (mod\ 4)$ 则为QR，$p \equiv 3\ (mod\ 4)$ 则为NR

Theorem 21.3 (Primes 1 (Mod 4) Theorem). There are infinitely many primes that are congruent to 1 modulo 4.

Theorem 21.4 (Quadratic Reciprocity). (Part II) Let p be an odd prime. Then 2 is a quadratic residue modulo p if p is congruent to 1 or 7 modulo 8, and 2 is a nonresidue modulo p if p is congruent to 3 or 5 modulo 8. In terms of the Legendre symbol,

$$(\frac{2}{p}) = \begin{cases} 1\quad if\ p \equiv 1\ or\ 7 \ (mod\ 8), \newline -1\quad if\ p \equiv 3\ or\ 5 (mod\ 8). \end{cases}$$

2QR还是NR？这个取决于质数p，若 $p \equiv \pm1\ (mod\ 8)$ 则为QR，$p \equiv \pm3\ (mod\ 8)$ 则为NR

$(\frac{a}{p}) = (\frac{q_1}{p})(\frac{q_2}{p}) \ldots (\frac{q_r}{p})$ $\dashrightarrow$ If we know how to compute $(\frac{q}{p})$ for primes $q$, then we know how to compute $(\frac{a}{q})$ for every $a$.

Yet another instance of the principle that primes are the basic building blocks of number theory. 另外一个质数是数论基石的实例。

Theorem 22.1 (Law of Quadratic Reciprocity). Let p and q be distinct odd prims. $$(\frac{-1}{p}) = \begin{cases} 1\quad if\ p \equiv 1 \ (mod\ 4), \newline -1\quad if\ p \equiv 3 \ (mod\ 4). \end{cases}$$ $$(\frac{2}{p}) = \begin{cases} 1\quad if\ p \equiv 1 \ or\ 7\ (mod\ 8), \newline -1\quad if\ p \equiv 3\ or\ 5 \ (mod\ 8). \end{cases}$$ $$(\frac{q}{p}) = \begin{cases} (\frac{p}{q})\quad if\ p \equiv 1 \ (mod\ 4)\ or\ q \equiv 1\ (mod\ 4), \newline -(\frac{p}{q})\quad if\ p \equiv q \equiv 3 \ (mod\ 4). \end{cases}$$ 二次互反律，可以用来计算$(\frac{a}{p})$。不必质因数分解a。

Jacobi symbol: $(\frac{a}{b}) = (\frac{a}{p_1})(\frac{a}{p_2})…(\frac{a}{p_r})$. 雅可比符号

Theorem 22.2 (Generalized Law of Quadratic Reciprocity). Let a and b be odd positive integers. $$(\frac{-1}{b}) = \begin{cases} 1\quad if\ b \equiv 1 \ (mod\ 4), \newline -1\quad if\ b \equiv 3 \ (mod\ 4). \end{cases}$$ $$(\frac{2}{b}) = \begin{cases} 1\quad if\ b \equiv 1 \ or\ 7\ (mod\ 8), \newline -1\quad if\ b \equiv 3\ or\ 5 \ (mod\ 8). \end{cases}$$ $$(\frac{a}{b}) = \begin{cases} (\frac{b}{a})\quad if\ a \equiv 1 \ (mod\ 4)\ or\ b \equiv 1\ (mod\ 4), \newline -(\frac{b}{a})\quad if\ a \equiv b \equiv 3 \ (mod\ 4). \end{cases}$$

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26  # WRONG, DONT USE! def qr(a, b): ''' Return 1 if equation x^2 ≡ a (mod b) has solutions, -1 otherwise ''' if a > b: a, b = b, a res = 1 while a != b - 1 and a != 2 and a != 1 and a != 0: count = 0 while a & 1 == 0: # a is even a = a // 2 count += 1 if count & 1: # count is odd if b % 8 == 3 or b % 8 == 5: res *= (-1) if a % 4 == 3 and b % 4 == 3: res *= (-1) a, b = b % a, a if a == b - 1: if b % 4 == 3: res *= (-1) if a == 2: if b % 8 == 3 or b % 8 == 5: res *= (-1) return res 

## Chap.23 Proof of Quadratic Reciprocity

$$(\frac{q}{p})(\frac{p}{q}) = (-1)^{\frac{p-1}{2} \frac{q-1}{2}}$$

In this chapter we build upon the ideas used to prove the second part to give Eisenstein’s proof of the third part.

Let $\mu(a,p)$ = ( number of integers in the list $a, 2a, 3a, …,Pa$ that become negative when the intergers in the list are reduced modulo $p$ into the interval from $-P$ to $P$ ).

Theorem 23.1 (Gauss’s Criterion). Let $p$ be an odd prime, let $a$ be an interger that is not divisible by $p$. Then

$$(\frac{a}{p}) = (-1)^{\mu(a,p)}.$$