1~10中与10互素的数有多少个？

　　2019年8月6日星期二

　　也许您看到这个题目，会和我一样认为十分简单，甚而至于您也会这样做：

　　（1，10）＝1

　　（2，10）＝2

　　（3，10）＝1

　　（4，10）＝2

　　（5，10）＝5

　　（6，10）＝2

　　（7，10）＝1

　　（8，10）＝2

　　（9，10）＝1

　　（10，10）＝10

　　答：1～10中与10互素的数是｛1，3，7，9｝，一共有4个。

　　上述计算过程用的是罗列法，写法上（a，b）表示求正整数a、b的最大公因数。事实上，a、b可以是任意整数Z，限定为正整数Z+，只是为了讨论问题的方便，负整数据说只需在正整数结论的基础上添加负号即可。

　　什么是a、b的最大公因数？

　　令d＝（a，b），对于其他任意的a、b的公因数c，都有c｜d（c整除d）。

　　以前，我总认为：最大公因数是公因数中最大的。现在，才知道这种说法是不准确的，因为有特例的存在。比如：0是0和0的最大公因数。所有自然数都能整除0，我一开始觉得，0和0没有最大公因数，因为找不出最大的自然数，然而，殊不知，“所有自然数都能整除0”，恰好说明“0是0和0的最大公因数”，根据上面的定义。

　　这是一点小插曲，串台了。

　　什么是a、b“互素”？

　　若（a，b）＝1，则a与b互素。

　　如果将问题改为：1~60中与60互素的数有多少个？

　　您也许会稍微嫌烦，但依旧可以“罗列”出来。

　　一共有16个，分别是｛1，7，11，13，17，19，23，29，31，37，41，43，47，49，53，59｝。

　　再进一步：1~1800中与1800互素的数有多少个？

　　这时，您也许会畅想用计算机解决，一般地，我也是这么想的。我们大多数都是平凡的人。

　　然而，早在1946年世界上第一台计算机诞生之前约200年左右，这个问题就被人称“神挡杀神，佛挡杀佛”的数学英雄欧拉完整而漂亮地解决了。也许您会在许多领域都会遇到冠名“欧拉公式”的数学结论，本文谈到的只是其中一个，诚如沧海一粟。

世界上第一台计算机（网络截屏）

欧拉简介（网络截屏）

　　“欧拉大神”大致是这样做的：

　　（一）对于任意的m∈Z+，且m＞1，都有唯一的标准分解式：

式1

　　其中：pi（i＝1、2……s）是素数（或质数），且p1<p2<……<ps，ri（i＝1、2……s）是非负整数。

　　例：

　　这个东西其实并不高深，类似于小学的“质因数分解”，高深的在下面。

　　（二）对于任意的m∈Z+，且m＞1，在1～m中与m互素的数的个数，记为欧拉函数φ（m），若m具有“式1”中的标准分解式，则有：

欧拉函数

　　例：

　　最后，请您不要问我为什么，我水平有限，就让我们静悄悄地做一些验证吧。

　　致敬大神，先从做一个“知道分子”开始。