这里不打算按顺序介绍数论。我自己挑选了一些比较有意思的专题在这里略述一下，希望大家能发现数论的乐趣。

首先要说的是，数论是非常难的。你只能努力地在其中寻找乐趣，而不能指望轻易地掌握数论。

我们下面就进入今天讨论的内容：同余与欧拉函数φ(n)。

同余应该是大家耳熟能详的内容了：如果a = b + dm 其中(a, b, d, m ∈ Z)，那么称a与b对模m同余。通俗点说就是a, b 除以m得到的余数相等。记作a ≡ b (mod m)。这个式子也等价于 m | (a - b)。

接着，我们看一个经典的例子：假如今天是星期天，则100^10000000天后是星期几？这个问题转化为数学语言，相当于要计算100^100000除以7的余数。常用计算机的同学很快可以通过log(10000000)的算法来求得这个结果。然而，我们这里将要给出如何笔算出这个结果，以至于计算出100^(7^1000000) mod 7这样的结果；或乃至更广泛的a^b^c^d^...mod k这样的式子的结果

这里就要引入欧拉函数了。我们定义欧拉函数φ(n)=|S|(或称集合S中元素的个数，也有记作card(S))，其中S={x∈N: 0<x≤n，且 (n, x) = 1}。用语言描述就是小于等于n且与n互质的正整数的个数。
关于欧拉函数的计算：有以下定理，这里不一一证明，事实上证明并不很困难，大家可以自己试试
(1)若p为质数则 φ(p) = p - 1
(2)若p为质数则 φ(p^k) = p^k - p^(k-1)
(3)若(m, n) = 1，则φ(mn)=φ(m)φ(n)
通过以上几个定理可以快速地计算任何一个数的欧拉函数。注意φ(1)=1。

介绍完欧拉函数的基本概念，这里插入一个有意思的定理：假设d1,d2,...,dk是n的全部约数。则φ(d1)+φ(d2)+...+φ(dk)=n。你可以自己试一下：比如15的约数有1 3 5 15，则φ(1)+φ(3)+φ(5)+φ(15)=1 + 2 + 4 + 8 = 15。

接着回到我们讨论的内容，欧拉函数与前面的同余的联系在哪里呢？这就要牵扯到著名的欧拉定理了。
欧拉定理：设m是一个大于1的整数，a是一个整数，并且(m, a) = 1。则有：m | (a^φ(m) - 1)。
加上前面的欧拉函数计算定理(1)：若p为质数则 φ(p) = p - 1，我们便得到了著名的费马定理：若p为一个素数，则a^(p-1)≡1 (mod p)。这个已经称为验证素数的高效算法的一个基础定理了。

接着我们再往回看100^10000000 mod 7 = ? 我们注意到7是一个素数，那么100^6 mod 7 = 1无疑了。又10000000 mod 6 = 4。 所以原式 = (100^6) ^ q (100 ^ 4) mod 7 = 2 ^ 4 mod 7 = 2。那么这天就是星期二了。
用同样的方法我们再来计算100^(100^1000000)天后的结果。第一步同上，我们接着要算7^1000000 mod 6的结果了。由φ(6) = 2，所以7^2 mod 6 = 1，也就是说7^1000000 mod 6 = 1!。那么我们问题的结果简单的变成了计算100 mod 7 = 2。所以这一天还是星期二。
至于更一般的情形，相信大家自己也可以计算了。但是要注意的是欧拉定理中有一个限制性很大的条件(m, a)= 1。那么大家肯定很想知道如果(m, a)≠1的时候，怎么计算出前面的式子的结果。这里提示一下要运用中国剩余定理（有的书上也称之为孙子定理），由于篇幅问题（也可以说我比较懒），这里就不介绍了。