今天我花了4个小时来看一本名为《数论与密码》的科普书。当我看到RSA公匙加密一节讲述证明欧拉定理时，我瞬间傻b了。
欧拉定理其实就是：a^φ(n) ≡ 1 (mod n)。其中a与n互素（所谓互素就是a与n的最大公约数是1，这可是一个比较优雅的定义），φ(n)是从1到n-1这n-1个正整数中与n互素的数的个数（我语言功底不好），例如φ(4)=2，其中1,3与4互素。书中大概是这么证明这个定理的：
我们有r1,r2,r3,……rφ(n)这个φ(n)个数。如果有r1r2r3…….rφ(n)a^φ(n) ≡ r1r2r3…….rφ(n) (mod n) 等式成立（号就是乘号），定理得证，因为我们可以从这个≡等式的两边同时除以r1r2r3…….rφ(n)，得定理等式，而这是为什么≡等式两边同时除以这个等式还能成立？
这就是初等数论中的消去律。所谓消去律：如m>=2,a与m互素，如果ab ≡ ac (mod m)，则b≡c (mod n)。这个证明是很简单且符合我们的直觉，所以这里我不给予说明。
这里令我迷惑的是为什么会有等式r1r2r3…….rφ(n)a^φ(n) ≡ r1r2r3…….rφ(n) (mod n) 的成立。我在网上找了一下，其实都没有根本说明这个问题，就是说在我觉得关键的地方跳了一步，而且多数解答都是复制百度百科。关键点：若x,y都和z互素则xy (mod z) 也会与z互素。所以 r1a（r1与a都与n互素） mod n 是一个素数，r1r2r3…….rφ(n)a^φ(n) 其实就是φ(n)个素数相乘，且这些素数都是不相同的，所以等于r1r2r3…….rφ(n)。为什么这些素数是不相同的？假如有两个数相同（i,j），则a*（i-j）(mod n)=0,这意味着n能整除（i-j），但i,j都是从r1到rφ(n)中选出来的，而r1到rφ(n)都是小于n（从定义可得）的，这却意味着n不能整除（i-j）所以得到矛盾。我就一直困惑于我所谓的关键点。
其实这也是很简单的，至少比后来的证明要简单，但由于我已经看过费马小定理的证明（欧拉定理时费马小定理的推广）所以觉得理所当然。
x,y都和z互素，令xy (mod z)=w ，我们用反证法证明，假设w与z不互素，则有大于1的公约数。xy=某数z+w=其大于1的公约数（某数q(q=z/大于1的公约数)+p（p=w/大于1的公约数）而x,y与z是没有大于1的公约数的，所以这个等式左边没有大于1的公约数，而右边有，所以等式不成立，所以xy (mod z) 也会与z互素。于是整个欧拉定理得证。
其实这是一个很简单的问题，但我却想了很久，原因在于我一边在想证明，一边在ubuntu社区闲逛，偶尔脑子里还冒出王小波优美的句子，导致了效率的低下。我们要高效地解决问题一定要专注。专注能让思想流动起来，进入某种状态，才能产生杰出的创造力。