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.

上式可以任意生成primitive Pythagorean triples。

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

整除的定义 (divisibility)

最大公因数的定义 (Greatest common divisor)

互质的定义 (relatively prime)

如何找两个数的最大公因数? –> Euclidean algorithm

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

即使a, b很大,用上面这个方法也可以在极短时间内找到两者的最大公因数。

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

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 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 = in exactly one way.



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

类似于Lemma 9.2.

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

一元数集Ring mn与二元点集Ring m, Ring 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.


# 适用于模数两两互质的情况,可以直接通过构造求解。
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

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.18 Powers, Roots, and “Unbreakable” Codes


Chap.19 Primality Testing and Carmichael Numbers

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


思路1: 质数必定满足费马小定理(Theorem 9.1.),如果不满足则必为合数。但是也有全都满足费马小定理的合数,即Carmichael number。 Theorem 19.1 (Korselt’s Criterion for Carmichael Numbers). Let n be a composite number. Then n is a Carmichael number if and only if it is odd and every prime p divding n satisfies the following two conditions: (1) p^2 does not divide n. (2) p - 1 divides n - 1.

思路2: Theorem 19.2 (A Property of Prime Numbers). Let p be an odd prime and write p - 1 = 2^k * q with q odd. Let a be any number not divisible by p. Then one of the following two conditions is true: (i) a^q is congruent 1 to modulo p. (ii) One of the numbers a^q, a^(2q), a^(4q), ..., a^(2^(k-1) * q) is congruent to -1 modulo p.

既然有a^(p-1) ≡ 1 (mod p),那么对此开根之前的数必定已经≡ 1或者≡ -1

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

线性同余方程的解已经在 Theorem 8.1. 中给出了方法。 但是非线性的同余方程呢?例如: $x^2 \equiv -1\ (mod\ 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).$$

欧拉判别。由费马小定理有a^(p-1) ≡ 1 (mod p),那么对左边开根,开根结果只有1 or -1,如果是1则说明a是QR,-1则为NR

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.

有无数质数 $p \equiv 1\ (mod\ 4)$ 。与Theorem 12.2.相对应。


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

Chap.22 Quadratic Reciprocity

$(\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}$$


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

同余方程 $x^2 + ax + b ≡ 0\ (mod\ p)$ 有解 $\iff$ $(\frac{\Delta\ =\ a^2 - 4b}{p}) = 1$。

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


Lemma 23.2. When the numbers $a, 2a, 3a, …, Pa$ are reduced modulo $p$ into the range from $-P$ to $P$, the reduced values are $\pm1$, …, $\pm$$P$ in some order, with each number appearing once with either a plus sign or a minus sign. 映射后(除去符号)没有重复。

Lemma 23.3. Let $p$ be an odd prime, let $P = \frac{p-1}{2}$, let $a$ be an odd integer that is not divisible by $p$, and let $\mu(a,p)$be the quantity defined above that appears in Gauss’s criterion. Then

$$\sum_{k=1}^{P} \left \lfloor \frac{ka}{p} \right \rfloor \equiv \mu(a,p) \ (mod\ 2).$$

piece of the proof of Quadratic Reciprocity:

$$\mu(q,p) + \mu(p,q) \equiv \frac{p-1}{2} \centerdot \frac{q-1}{2} \ (mod\ 2).$$


Chap.24 Which Primes Are Sums of Two Squares?

Which numbers can be written as sums of two squares?

Theorem 24.1 (Sum of Two Squares Theorem for Primes). Let $p$ be a prime. Then $p$ is a sum of two squares exactly when

$$p \equiv 1 \ (mod\ 4) \qquad \qquad (or\ p = 2).$$


Descent Procedure

Chap.25 Which Numbers Are Sums of Two Squares?

A product of sums of squares can be expressed by a sum of squares:

$$(u^2 + v^2)(A^2 + B^2) = (uA + vB)^2 + (uA - vB)^2.\qquad\qquad\qquad(*)$$

Divide and Conquer Divide: Factor $m$ into a product of primes $p_1p_2…p_r$. Conquer: Write each prime $p_i$ as a sum of two squares. Unify: Use the identity (*) repeatedly to write $m$ as a sum of two squares.

Theorem 25.1 (Sum of Two Squares Theorem). Let $m$ be a positive integer. (a) Factor $m$ as $m = p_1p_2…p_rM^2$ with distinct prime factors $p_1, p_2, …, p_r$. Then $m$ can be written as a sum of two squares exactly when every $p_i$ is either 2 or is congruent to 1 modulo 4. (b) The number $m$ can be written as a sum of two squares $m = a^2 + b^2$ with $gcd(a, b) = 1$ if and only if it satisfies one of the following two conditions:  (i) $m$ is odd and every prime divisor of $m$ is congruent to 1 modulo 4.  (ii) $m$ is even, $m/2$ is odd, and every prime divisor of $m/2$ is congruent to 1 modulo 4.


Theorem 25.2 (Pythagorean Hypotenuse Proposition). A number $c$ appears as the hypotenuse of a primitive Pythagorean triple $(a, b, c)$ if and only if $c$ is a product of primes each of which is congruent to 1 modulo 4.

Chap.26 As Easy as One, Two, Three

Many number theoretic assertions have the form: Such and such a statement is true for every natural number $n$. For example:

  • $1^2 + 2^2 + … + n^2 = \frac{2n^3 + 3n^2 + n}{6}$ for every $n \in \mathbb{Z}$.
  • Every natural number $n$ is equal to a product of prime numbers.
  • Every natural number $n$ is equal to a sum of at most four squares.

Principle of Mathematical Induction

  • Step I (Initialization) Check the initial case $n = 1$.
  • Step II (Induction Step) Assume that we’ve already completed the proof for all values up to $n$, and using this assumption, which is called the induction hypothesis, prove the statement for $n + 1$. 数学归纳法

Complete induction or strong induction

  • Step I (Initialization) Check the initial case $n = 1$.
  • Step II (Induction Step) Assume that we’ve already completed the proof for all values of $n$ satisfying $1 \leqslant n \leqslant N$, and using this assumption, prove that the statement is true for $n = N + 1$. 强数学归纳法

Chap.27 Euler’s Phi Function and Sums of Divisors

Define a function $F(n) = \phi(d_1) + \phi(d_2) + … + \phi(d_r),\qquad\qquad where\ d_1, d_2, …, d_r\ are\ the\ divisors\ of\ n$.

Lemma 27.1. $I!f\ gcd(m, n) = 1,\ then\ F(mn) = F(m)F(n)$.

sum(phi(di) where di | n) = n


Chap.28 Powers Modolu p and Primitive

Primitive Roots (原根): a^x 能生成所有在{1, 2, …, p-1}内的数,质数p一共有phi(p-1)个原根

Chap.29 Primitive Roots and Indices

{g^1, g^2, g^3, …, g^(p-1)}与{1, 2, 3, …, p-1}一一对应。但是对应关系没有规律,也就是discrete,DLP正基于这一点。

Chap.30 The Equation X^4 + Y^4 = Z^4

方程$x^4 + y^4 = z^2$没有正整数解。

Chap.31 Square-Triangular Numbers Revisited

既是平方数又是三角数的数叫做square-triangular number,有无数个这样的数。 求平方数可以归于求方程$x^2 - 2y^2 = 1$的正整数解。 方程的解可以由$x_k + y_{k}\sqrt2 = (3 + 2\sqrt2)^k$生成。

Chap.32 Pell’s Equation

形如$x^2 - Dy^2 = 1$(其中D是一个非完全平方数的正整数)的方程叫做佩尔方程(Pell equation)。 该方程被Brahmagupta, Bhaskaracharya和Brouncker研究过,更应被称为$B^3$ equation。 方程总有正整数解,如果$(x_1, y_1)$是最小解,那么所有解可以由$x_k + y_{k}\sqrt{D} = (x_1 + y_{1}\sqrt{D})^k\qquad for\ k = 1,2,3,…$生成。

Chap.33 Diophantine Approximation

丢番图逼近,丢番图分析?? Dirichlet’s approximation theorem 有无数对正整数满足$|x - y\alpha| < \frac{1}{y}$,其中$\alpha > 0$是无理数。

Chap.34 Diophantine Approximation and Pell’s Equation

Diophantine Approximation证了一下佩尔方程有无数解和解的形式。(很难看懂)

Chap.35 Number Theory and Imaginary Numbers

虚数$i = \sqrt{-1}$

Theorem 35.1 (The Fundamental Theorem of Algebra). If $a_0, a_1, a_2, …, a_d$ are complex numbers with $a_0 \ne 0$ and $d \ge 1$, then the equation

$$a_0x^d + a_1x^{d-1} + a_2x^{d-2} + … + a_{d-1}x + a_d = 0$$

has a solution in complex numbers.

We do number theory with a certain subset of the complex numbers called the Gaussian integers. These are the complex numbers that look like $a + bi$ with $a$ and $b$ both integers.

Gaussian primes

为什么要扯上虚数? for $(a + bi)(a - bi) = a^2 + b^2$

Theorem 36.1 (Unique Factorization of Gaussian Integers). Every Gaussian integer $\alpha \ne 0$ can be factored into a unit $u$ multiplied by a product of normalized Gaussian primes $\alpha = u\pi_1\pi_2…\pi_r$ in exactly one way.


We use the Gaussian Integer Unique Factorization Theorem to count how many different ways a number can be written as a sum of two squares.

Theorem 36.5 (Sum of Two Squares Theorem(Legendre)). For a given positive integer N, let $D_1$ = (the number of positive integers d dividing N that satisfy $d \equiv 1\ (mod\ 4)$), $D_3$ = (the number of positive integers d dividing N that satisfy $d \equiv 3\ (mod\ 4)$). Then N can be written as a sum of two squares in exactly $R(N) = 4(D_1 - D_3)$ ways.

Chap.37 Irrational Numbers and Transcendental Numbers

整数 -> 有理数 -> 无理数

algebraic number(代数数): 能成为整系数多项式的根。 transcendental number(超越数): 非代数数。

One of the most beautiful theorems in transcendence theory was proved independently by A.O Gelfond and T.Schneider in 1934. They showed that if $a$ is any algebraic number other than 0 or 1 and if $b$ is any irrational algebraic number, then the number $a^b$ is transcendental.


Chap.38 Binomial Coefficients and Pascal’s Triangle


$(A + B)^p \equiv A^p + B^p\ (mod\ p)$,利用该定理,可以用(强)数学归纳法来证明费马小定理。

Chap.39 Fibonacci’s Rabbits and Linear Recurrence Sequences

$$F_n = \frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^2 - (\frac{1-\sqrt{5}}{2})^n]$$


Chap.40 Oh, What a Beautiful Function

介绍了$O(f(n))$,也就是*‘big-Oh’ notation*。

$O(\log{n})$ is said to take linear time.


Chap.41 Cubic Curves and Elliptic Curves

$E: y^2 = x^3 + ax^2 + bx + c$,其中$a, b, c$均为整数。

If $\vartriangle!(E) = -4a^3c + a^2b^2 - 4b^3 - 27c^2 + 18abc \ne 0$, there are only finetely many solutions in integers x and y。

Chap.42 Elliptic Curves with Few Rational Porints


Chap.43 Points on Elliptic Curves Modulo p



p-defect: $a_p = p - N_p$

Chap.44 Torsion Collections Modulo p and Bad Primes

In general, we say that $p$ is a bad prime for an elliptic curve $E: y^2 = x^3 + ax^2 + bx + c$ if the polynomial $x^3 + ax^2 + bx + c$ has a double or triple root modulo $p$.

Chap.45 Defect Bounds and Modularity Patterns

Hasse’s Theorem: $$|a_p| < 2\sqrt{p}$$

Modularity Patterns

Chap.46 Elliptic Curves and Fermat’s Last Theorem

  1. let $p \ge 3$ be a prime, and suppose that there is a solution (A, B, C) to $A^p + B^p = C^p$ with A, B, C nonzero integers and $gcd(A,B,C) = 1$.
  2. Let $E_{A,B}$ be the Frey Curve $y^2 = x(x + A^p)(x - B^p)$.
  3. Wiles’s Theorem tells us that $E_{A,B}$ is modular; that is, its $p$-defect $a_p$ follow a modularity pattern.
  4. Ribet’s Theorem tells us that $E_{A,B}$ is so strange that it cannot possibly be modular.
  5. The only way out of this seeming contradiction is the conclusion that the equation $A^p + B^p = C^p$ has no solutions in nonzero integers.

It is here, at the successful resolution of this most famous problem in mathematics, that we end our voyage through the Seven Seas of Number Theory. I hope you have enjoyed the tour as much as I have enjoyed being your guide and that you have found much to admire and much to ponder in this most beautiful of subjects. Above all, I hope that you have gained a sense of mathematics as a living, growing enterprise, with many wonderful treasures already discoveredm, but with many others, even more wonderful, waiting just over the horizion for the person having the insight, the daring, and the perseverance to sail into the unknown.




自今年5月开始看youtube上一个关于密码学的lecture以来,我发现的确学到了许多东西。lectures只看了一半,后来觉得lectures上面虽然教授讲得很棒,但还是有一些额外的东西没有涉及到,所以就直接找到了教授Paar写的书,也就是看的第一本密码学书籍Understanding Cryptography。书里讲得更棒了,有多棒呢?棒到如果有人想入门密码学,我会第一个推荐这本书。书里不光讲了各种加密算法的具体实现,还附带一些常见的攻击方式以及拓展知识,看完这本书,基本上就能对密码学有一个比较大概的理解。CTF题做起来也变得很顺滑了,基本上能应付得了超过一半的密码题。在看lectures和书的同时,我也按照书(lectures)上的叙述,用Python实现了一遍大部分加密算法,可以在我的github上找到(还有后面一部分没完成)。看完书后,感觉意犹未尽,感觉密码学的学习不应该蜻蜓点水、就此而止,于是就在知乎上找到了一篇求大触们推荐一些比较系统的关于密码加密解密的书籍?。想跟着里面的书单学一下,所以就直接上手了这本A Friendly Introduction to Number Theory



书里有一个很吸引我的地方,就是关于是否有无数个平方三角数。我上高三的时候,快到高考了,很无聊,就各种没事找事,手算2的100次方、手算3的100次方,后来找上了这个n(n+1)/2是平方数的问题。那个时候还尝试过用高一学过的一点Visual Basic写了个代码,跑了下,发现是有挺多个的,到后面都很大,不过并不会用严格的数学语言来证明,那个时候好像也推到了$x - 2y^2 = 1$这一步。所以在书的一开头我就又看到这个问题,自然十分欣喜,所有就有一种想继续看下去,在书的后面去找答案的冲动,所幸找到了答案,也学习了很多别的东西。

先吹一波这个作者的文笔,是真的挺好的。就单凭第二章数论之美以及最后一章继续远行,我就被折服了,或许这就是看英文原版书籍的好处吧。作者不光文笔好,写的东西也很能引人入胜,很多定理都是先由一些对数字的观察,发现patterns后,再去给出证明的,而且在给出一长串证明的时候,能够将大证明拆成小证明,再结合许多个小证明来完成大证明。这就相对于那些直接给定理和证明的就有意思多了,这种方式更能启发读者自己的思考,能有自己的发现过程。或许这就是作者想要传授给我们的sence of mathematics吧。



数论稍微了解了下,接下来的打算就是An Introduction to Mathematical Cryptography了,毕竟我感觉密码学里面最美妙的莫过于公钥密码了。

Load Comments?