1. Divisible?

$4^{1536}-9^{4824}$是否能被35整除？

$35=5\times 7$，根据费马小定理：$a^{5-1}\equiv 1 (\mod 5)$，$a^{7-1}\equiv 1(\mod 7)$，由于5和7都是素数，易得：$a^{(5-1)(7-1)}\equiv 1(\mod 35)$，即$a^{24}\equiv 1(\mod 35),1\leq a<35$。因此$4^{1536}-9^{4824}\equiv 4^{24\cdot 64}-9^{24\cdot 201}\equiv 1-1(\mod 35)$，故$4^{1536}-9^{4824}$能被35整除。

1. 费马素性测试-1

上一章提到过两数互质的问题，质数（素数）一直以来都是数论中的重点内容。一个基本问题就是：如何判断一个数是否为素数？最容易想到的方法：将这个数做质因数分解，若因数只有1和它本身，则为素数，但是质因数分解效率很低；另一种方法是，依次判断是否有比它小的数整除它，本质上还是质因数分解。下面要介绍的一种高效的素性测试方法，基于一个重要的定理：

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$位。