1. 辗转相除法(Euclid’s algorithm)

有了模运算，我们可以利用它解决不少关于数字的问题。其中，最为著名的问题当属求解两个数的最大公因数(gcd, greatest common divisor)。最容易想到的方法就是，先对两数分别做质因数分解（factoring），然后将它们相同的质因子相乘得到结果。如：$1035=3^3\cdot 5\cdot 23,759=3\cdot 11\cdot 23,gcd(1035,759)=3\cdot 23=69$。不幸的是：

目前还没有足够高效的分解质因数的算法。

1. 模运算

我们知道，计算机处理器进行内置的算术运算时，数字大小都是有限制的（32 bits or 64 bits），这已经可以满足绝大多数计算需求了。但如果不断地对一个数做加法或乘法运算，它将变得非常大，最终将会溢出(overflow)。如何解决这个问题？可以从日常生活中得到启发：日复一日，年复一年… 第二天又是新的24小时，第二年又是新的十二个月…

1. $n-bit$乘法的原理与实现

小学的时候就学过乘法的竖式计算，二进制乘法步骤如下：

1
2
3
4
5
6
7
8
9

              1 1 0 1    (13)
            × 1 0 1 1    (11)
------------------------
              1 1 0 1    (1101×1)
            1 1 0 1      (1101×1, shift left once)
          0 0 0 0        (1101×0, shift left twice)
      + 1 1 0 1          (1101×1, shift left thrice)
------------------------
      1 0 0 0 1 1 1 1    (143)

1. 浅谈基数(base)和$\log$

这章主要研究的对象是数字，首要的问题是，如何表示数字？众所周知，目前我们日常使用的都是十进制表示法（可能因为有十个手指头吧），计算机内部使用的都是二进制表示法。这里的“十”、“二”就是基数(base)。

假设现在用$b(b\geq 2)$-进制表示法。第一个问题，表示一个正整数$N\geq 0$需要至少多少位？我们知道，$k$位数字最大是$b^k-1$，那么可以推导出我们至少需要$\lceil \log_b (N+1) \rceil$位。

1. Fibonacci数列

Fibonacci是15世纪意大利著名的数学家，虽然大多数人不太清楚他的具体贡献，却都对Fibonacci数列耳熟能详：

$$
0,1,1,2,3,5,8,13,21,34
$$

我们设Fibonacci数列的第$n$项的值为$F_n$，则数列的每一项可以由以下递推式生成：

$$
\begin{equation}
F_n=
\begin{cases}
F_{n-1}+F_{n-2}, & n>1 \\ 1, & n=1 \\ 0, & n=0
\end{cases}
\end{equation}
$$