今天我们来讲一讲如何求小于某正整数且与这个正整数互素的正整数的个数。比如说，某个正整数是8，则小于8且与8互素的正整数有：1,3,5,7，共4个（2,4,6这三个数都与8有公因数2，所以都不符合要求；其中的4甚至与8有4这个公因数）。再比如某个正整数是9，则小于9且与9互素的正整数有：1,2,4,5,7,8，共6个（3和6都与9有公因数3，所以不符合要求）。8和9都是比较小的数，我们靠列举法可以找出这些数，但对于比较大的数，则不太容易列举。有时我们只是为了求出符合要求的正整数的个数，不想知道具体是什么。所以，我们就必须找到一种通用的方法。

小于某正整数且与这个正整数互素的正整数的个数在素数理论中非常重要。比如，我之前讲过费马小定理，但其实费马小定理只是规律更加普遍的欧拉定理的特殊情况。欧拉定理就用到这个个数。后面我们将看到，这个个数可以通过欧拉函数（即下面我们将要讲到 的φ(m) ）求得。我们可以比较一下费马小定理与欧拉定理（在下面用蓝字显示，您可以跳过不看，不影响后面的阅读）。

费马小定理 ：若p是素数，n为一个不能被p整除的正整数，则

能被p整除。

欧拉定理 ：有正整数m与n，m与n互素。设φ(m)为小于m且与m互素的正整数的个数。那么，

能被m整除。 其中的φ(m)叫做欧拉函数。

当m为素数时，小于m的正整数都与m互素，这样的数一共有m － 1个，即 φ(m) = m － 1 。这时的欧拉定理就成为费马小定理。

欧拉函数很重要，我们必须会求它的值。这个函数的表达式如下：

其中的 p 1 ， p 2 ，…， p k 来自m的标准分解式：

其中 p 1 ， p 2 ，…， p k 都为素数，且 p 1 < p 2 <…< p k。 α 1 ，α 2 ， …， α k 是确定的正整数。 这个标准分解式叫做一个正整数的素因数分解。这个标准分解式是唯一的。

我们可以用这个公式计算一下开篇时提到的数8和9。m=8时，m的素因数分解式为：

这时只有p 1 一个素数，p 1 =2。代入欧拉函数中，得到

m=9时，m的素因数分解式为：

这时也只有p 1 一个素数，p 1 =3。代入欧拉函数中，得到

我们再来看另一个数m=15。m的素因数分解为：m=15=3×5。所以p 1 =3，p 2 =5。所以，

我们可以用列举法验证一下。把小于15的正整数列出来，数一数一共有多少个与15互素的数。小于15的14个正整数是：

1 , 2 ,3, 4 ,5,6, 7 , 8 ,9,10, 11 ,12, 13 , 14

其中标红的数字为与15互素的，共有8个。这与用欧拉函数计算出来的完全一样。

那么，欧拉函数的表达式，也就是计算小于某数且与这个数互素的正整数的个数的公式是怎么得到的呢？我们下面用一个具体的例子来讲解。

我们来看一看m=30。我们采取的方法是：找出小于等于30的正整数中与30 不互素 的数，计算出它们的个数，然后用30减去这个个数，就会得到小于30但与30 互素 的数的个数。这句话若还不好一下子理解，我们不妨先往下看。

30的素因数分解式为：30=2×3×5。它有三个不同的素因数：2,3,5。显然，小于等于30的正整数中，所有2的倍数都有2这个因数，而30也有2作为其因数。容易算得，共有 15个 小于等于30的2的倍数（30/2=15），它们都是与30不互素的。这15个数构成一个集合 A 2 ：

A 2={ 2 , 4 , 6 , 8 , 10 , 12 , 14 , 16 , 18 , 20 , 22 , 24 , 26 , 28 , 30 }

同理，小于等于30的正整数中，所有3的倍数都有3这个因数，而30当然也有3作为因数。容易算得，共有 10个 小于等于30的3的倍数（30/3=10），它们都是与30不互素的。这10个数 构成一个集合 A 3 ：

A 3 = { 3, 6, 9, 12, 15, 18, 21, 24, 27, 30 }

再同理，小于等于30的正整数中，所有5的倍数都有5这个因数，而30当然也有5作为因数。容易算得，共有 6个 小于等于30的5的倍数（30/5=6），它们都是与30不互素的。这6个数构成一个集合 A 5 :

A 5 ={ 5, 10, 15, 20, 25, 30 }

这些数就是小于30且与30不互素的正整数的全部了。那么我们把它们加进来，得：15+10+6=31。但这显然有问题：怎么可能小于30且与30不互素的正整数有31个呢？仔细观察容易看出，三个集合之间都有重复出现的数，比如6，比如15。我们所要寻找的与30不互素的数的全体，应该是上面三个集合的并集。我们来看下面这张图，它形象地把这些数的关系呈现了出来。我们就是要求所有出现在下图中的数的个数。

求三个集合的并集中元素的个数，用到的是容 斥原理（下式中绝对值表示的是集合的个数）：

| A 2 ∪ A 3 ∪ A 5 | = | A 2 | ＋ | A 3 | ＋ | A 5 |

－ | A 2 ∩ A 3 | － | A 2 ∩ A 5 | － | A 3 ∩ A 5 |

＋ | A 2 ∩ A 3 ∩ A 5 |

从上图中可以看出：

| A 2 | =15

| A 3 |=10

| A 5 |=6

A 2 ∩ A 3 = {6,12,18,24,30} → | A 2 ∩ A 3 |=5

A 2 ∩ A 5 ={ 10,20,30} → | A 2 ∩ A 5 |=3

A 3 ∩ A 5 ={ 15,30} → | A 3 ∩ A 5 |=2

A 2 ∩ A 3 ∩ A 5 ={30} → | A 2 ∩ A 3 ∩ A 5 |=1

代入就得到：

| A 2 ∪ A 3 ∪ A 5 |= 15＋10＋6 － 5 － 3 － 2+1=22

上式计算出了小于等于30的正整数中与30不互素的正整数的个数。那么，小于30的正整数中与30互素的正整数的个数就是30减去22，等于8。

其实，上面那个欧拉函数φ(m)就是利用容斥原理得到的。

在上式中用m=2×3×5代入，其中p 1 =2，p 2 =3，p 3 =5。

再举个例子。m=100。可以由欧拉函数求出小于100且与100互素的正整数的个数为：

所有偶数共50个要排除掉，还剩下 50个 。所有5的倍数共20个也要排除掉，这样就剩下 30个 了。但既是偶数又是5的倍数的数有10个，所以我们多排除了10个，需要再加回来10个。所以是 40个 。我们就是一个个地用心算，也可以找到这40个数：

1, 3, 7, 9, 11,13,17,19,

21,23,27,29, 31,33,37,39,

41,43,47,49, 51,53,57,59,

61,63,67,69, 71,73,77,79,

81,83,87,89, 91,93,97,99

我们今天把欧拉函数与容斥原理讲到一起了。其实就是这么回事，并不复杂。

有欧拉函数参与其中的欧拉定理，则与RSA密码有着密切的关系。RSA密码在互联网的传输中有着重要的应用。这里就不介绍了，以后有时间再说。 返回搜狐，查看更多