应用容斥原理推广欧拉函数_林才雄.pdf

《应用容斥原理推广欧拉函数_林才雄.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第３３卷第１期江苏师范大学学报（自然科学版）Ｖｏｌ．３３，Ｎｏ．１２０１５年２月ＪｏｕｒｎａｌｏｆＪｉａｎｇｓｕＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ（ＮａｔｕｒａｌＳｃｉｅｎｃｅＥｄｉｔｉｏｎ）Ｆｅｂ．，２０１５文章编号：２０９５－４２９８（２０１５）０１－００５２－０３应用容斥原理推广欧拉函数林才雄（华南师范大学数学科学学院，广东广州５１０６３１）摘要：利用容斥原理对欧拉函数进行了推广，得出如下结论：１）给出了欧拉函数的３种初步推广，即函数φｒ；ｋ（ｍ），Ωｒ；ｋ；ｌ（ｍ），Ｈｒ；ｋ；ｌ（ｍ），找到并证明了ｒ＝０的３个表达式；２）进一步推广了欧拉函数，得到并证明了函数φｒ；ｋ（ｍ），Ωｒ；ｋ

2、；ｌ（ｍ），Ｈｒ；ｋ；ｌ（ｍ）中ｒ取１，２，３的表达式与ｒ＝０的倍数关系．关键词：欧拉函数；容斥原理；推广中图分类号：Ｏ１５７．１文献标识码：Ａｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．２０９５－４２９８．２０１５．０１．００８ＰｏｐｕｌａｒｉｚａｔｉｏｎｏｆｔｈｅＥｕｌｅｒｆｕｎｃｔｉｏｎｂｙｕｓｉｎｇｔｈｅｐｒｉｎｃｉｐｌｅｏｆｉｎｃｌｕｓｉｏｎ－ｅｘｃｌｕｓｉｏｎｍｅｔｈｏｄＬｉｎＣａｉｘｉｏｎｇ（ＳｃｈｏｏｌｏｆＭａｔｈｅｍａｔｉｃａｌＳｃｉｅｎｃｅｓ，ＳｏｕｔｈＣｈｉｎａＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｇｕａｎｇｚｈｏｕ５１０６３１，Ｇｕａｎｇｄｏｎｇ，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ

3、：ＴｈｅｐｕｒｐｏｓｅｏｆｔｈｉｓｐａｐｅｒｉｓｔｏｐｏｐｕｌａｒｉｚｅｔｈｅＥｕｌｅｒｆｕｎｃｔｉｏｎｂｙｕｓｉｎｇｔｈｅｐｒｉｎｃｉｐｌｅｏｆｉｎｃｌｕｓｉｏｎ－ｅｘｃｌｕｓｉｏｎｍｅｔｈｏｄ．Ｔｈｅｆｏｌｌｏｗｉｎｇａｒｅｔｈｅｍａｉｎｃｏｎｃｌｕｓｉｏｎｓ：１）ＧｉｖｅｔｈｒｅｅｉｎｉｔｉａｌｐｒｏｍｏｔｉｏｎｏｆｔｈｅＥｕｌｅｒｆｕｎｃｔｉｏｎ，ｆｏｕｎｄａｎｄｐｒｏｖｅｄｔｈｅｅｘｐｒｅｓｓｉｏｎｓｗｈｅｎｒ＝０；２）Ｏｂｔａｉｎｅｄａｎｄｐｒｏｖｅｄｔｈｅｍｕｌｔｉｐｌｅｒｅｌａｔｉｏｎｓｈｉｐｓａｍｏｎｇｔｈｏｓｅｅｘｐｒｅｓｓｉｏｎｓｏｆｔｈｅｔｈｒｅｅｆｕｎｃｔｉｏｎｓ

4、ｗｈｅｎｒｔａｋｅｓ１，２，３ａｎｄｒｔａｋｅｓ０．Ｋｅｙｗｏｒｄｓ：Ｅｕｌｅｒｆｕｎｃｔｉｏｎ；ｉｎｃｌｕｓｉｏｎ－ｅｘｃｌｕｓｉｏｎｍｅｔｈｏｄ；ｐｏｐｕｌａｒｉｚａｔｉｏｎｍｍ－１），欧拉函数φ（ｎ）是数论中一个重要的函数，是数引理２１－ａ＝（１－ａ）（１＋ａ＋…＋ａ学家欧拉首先提出的．欧拉函数φ（ｎ）表示不大于自ｍ∈Ｎ＋．［６］然数ｎ且与ｎ互质的自然数的个数．易知φ（１）＝１，引理３自然数１，２，…，ｎ的ｍ（ｍ∈Ｎ＋）次ｎ（２）＝１，（３）＝２，（４）＝２，（５）＝４．该函数在很φφφφｍ幂和式∑ｉ是关于ｎ的一个ｍ＋１次的有理多项多领域中有广泛的应用，如在离散数学中求循环群ｉ＝１ｎ

5、ｍ＋１［１］的生成元，在计算机网络安全中的ＲＳＡ公开密钥式，即∑ｉｍ＝∑ａｉｎｉ，其中密码体制中的应用［２］等．ｉ＝１ｉ＝１ａｉ∈Ｑ，ｉ＝１，２，…，ｍ＋１．虽然关于欧拉函数的研究有很多，如欧拉函数定义１设ｍ（ｍ≥２）为自然数，ｐ１，ｐ２，…，ｐｋ［３］的性质、方程、算法实现以及欧拉函数在数论、抽是互异的质数，且都是ｍ的因数，记１，２，…，ｍ中不［４］象代数方面的推广等等，但在组合数学方面目前能被ｐ１，ｐ２，…，ｐｋ中的任何一个整除的自然数的ｒ尚未见相关的结果．因此，本文尝试利用容斥原次方和为φｒ；ｐ１，…，ｐｋ（ｍ），简记为φｒ；ｋ（ｍ）．［５］理，对欧拉函数进行若干推广．定理１设ｍ（ｍ

6、≥２）为自然数，ｐ１，ｐ２，…，ｐｋ是互异的质数，且都是ｍ的因数，则１，２，…，ｍ中不１欧拉函数的推广之一能被ｐ１，ｐ２，…，ｐｋ中的任何一个整除的自然数的个引理１（ｘ－ａ）（ｘ－ａ）…（ｘ－ａ）＝ｘｌ１２ｌ－数为ｌ－１ｌ－１ｌｋσ１ｘ＋…＋（－１）σｌ－１ｘ＋（－１）σｌ，其中１φ０；ｋ（ｍ）＝ｍ∏（１－）．（１）σｉ＝ａａ…ａ，ｉ＝１，２，…，ｌ．ｉ＝１ｐｉｊｊｊ∑１２ｉ１≤ｊ１＜…＜ｊｉ≤ｌ证记Ｓ＝｛１，２，…，ｍ｝，Ａｉ＝｛Ｓ中ｐｉ的倍收稿日期：２０１４－０４－２６作者简介：林才雄，男，硕士研究生，主要从事竞赛数学和初等数学方面的研究，Ｅ－ｍａｉｌ：１００２１０１６５６＠ｑｑ．ｃｏ

7、ｍ．引文格式：林才雄．应用容斥原理推广欧拉函数．江苏师范大学学报：自然科学版，２０１５，３３（１）：５２－５４．ＬｉｎＣａｉｘｉｏｎｇ．ＰｏｐｕｌａｒｉｚａｔｉｏｎｏｆｔｈｅＥｕｌｅｒｆｕｎｃｔｉｏｎｂｙｕｓｉｎｇｔｈｅｐｒｉｎｃｉｐｌｅｏｆｉｎｃｌｕｓｉｏｎ－ｅｘｃｌｕｓｉｏｎｍｅｔｈｏｄ．ＪＪｉａｎｇｓｕＮｏｒｍＵｎｉｖ：ＮａｔＳｃｉＥｄ，２０１５，３３（１）：５２－５４．第１期林才雄：应用容斥原理推广欧拉函数５３数