互素是什么意思?1~10中与10互素的数有多少个

 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年左右,这个问题就被人称“神挡杀神,佛挡杀佛”的数学英雄欧拉完整而漂亮地解决了。也许您会在许多领域都会遇到冠名“欧拉公式”的数学结论,本文谈到的只是其中一个,诚如沧海一粟。

互素是什么意思?1~10中与10互素的数有多少个世界上第一台计算机(网络截屏)

互素是什么意思?1~10中与10互素的数有多少个欧拉简介(网络截屏)

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

(一)对于任意的m∈Z+,且m>1,都有唯一的标准分解式:

互素是什么意思?1~10中与10互素的数有多少个式1

其中:pi(i=1、2……s)是素数(或质数),且p1<p2<……<ps,ri(i=1、2……s)是非负整数。

例:

互素是什么意思?1~10中与10互素的数有多少个

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

(二)对于任意的m∈Z+,且m>1,在1~m中与m互素的数的个数,记为欧拉函数φ(m),若m具有“式1”中的标准分解式,则有:

互素是什么意思?1~10中与10互素的数有多少个欧拉函数

例:

互素是什么意思?1~10中与10互素的数有多少个

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

互素是什么意思?1~10中与10互素的数有多少个

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表科普匠立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:https://www.kpjiang.com/p/28596.html

科普匠尊重原创版权,如若内容或图片造成侵权/违法违规/事实不符,请联系科普匠进行投诉反馈,一经查实,立刻删除!