初等数论c++
- 格式：doc
- 大小：51.50 KB
- 文档页数：17
下载文档原格式
合集下载
初等数论_精品文档
初等数论初等数论是数学中的一个分支，研究的是整数的性质和特殊的数学关系。
它是数学发展的基础，对于数学中的许多其他分支，如代数、几何和数值分析都具有重要的影响。
初等数论可以追溯到古希腊时代，当时的数学家们对整数之间的关系进行了研究，并推导出了许多重要的结论。
在初等数论中，最基础的概念是整数和素数。
整数是自然数、负自然数和零的总称，它们可以用来表示数量。
素数是只能被1和自身整除的正整数，它们没有其他的因子。
素数在初等数论中具有重要的地位，因为他们是其他整数的构成单元。
在初等数论中，我们可以探讨整数的因子分解。
因子分解是将一个整数表示为素数的乘积的过程。
例如，将数字20分解成素数的乘积可以得到2×2×5=20。
因子分解在数论中起着重要的作用，它有助于我们理解整数之间的数学关系。
初等数论中的另一个重要概念是最大公约数和最小公倍数。
最大公约数是两个整数中能够同时被整除的最大的正整数。
最小公倍数是能够同时整除两个整数的最小的正整数。
最大公约数和最小公倍数可以帮助我们解决一些实际问题，比如找到最简分数、解线性方程等。
初等数论中还有一个重要的概念是同余。
同余是指两个整数除以一个正整数得到的余数相同。
例如，当两个整数被3除得到的余数相同时，我们可以说这两个整数互为3的同余数。
同余关系在数论中起着重要的作用，它可以帮助我们研究整数之间的性质和特殊的数学规律。
初等数论还涉及到数论函数的研究。
数论函数是定义在整数上的函数，它们可以帮助我们描述整数的性质和特征。
常见的数论函数包括欧拉函数、莫比乌斯函数等。
这些函数在数论中有广泛的应用，可以帮助我们研究素数分布、整数方程的解等问题。
除了以上几个基本概念，初等数论还包括一些其他的内容，如二次剩余、费马小定理、威尔逊定理等。
这些概念和定理都有着重要的理论意义和实际应用。
初等数论在数学中具有广泛的应用。
它不仅是其他数学分支的基础，还有着许多实际应用。
例如，在计算机科学中，初等数论可以帮助我们设计和分析算法、构建密码系统等。
初等数论及其应用
= 7 × 85 + 5 × 84 + 3 × 83 + 4 × 82 + 0 × 8 + 1
= 251649
16
课堂练习
计算: 将237894与251649都转换为二进制.
解: 其八进制表示分别为(720506) 8与(753401)8
易知对八进制0 − 7有如下二进制转换
0 −> 000 1 −> 001 2 −> 010 3 −> 011
4 −> 100 5 −> 101 6 −> 110 7 −> 111
因此, (720506) 8 = (111010000101000110) 2
(753401) 8 = (111101011100000001) 2
17
总结
自然数或者正整数指的是数1, 2,…, 而整数指的是数
0,±1,±2,⋯. 全体整数的集合记为ℤ, 而全体正整数或
除法:
66 = 2 × 33 + 0 (低位)
33 = 2 × 16 + 1
16 = 2 × 8 + 0
8=2×4+0
4=2×2+0
2=2×1+0
1 = 2 × 0 + 1 (高位)
按从低位到高位顺序, 依次取出上述除法中的余数, 得到
(66)10 = (1000010)2.
12
余数的定义
定义1.1.2 带余除法 = + 中的为用除得出
② 如果|, ≠ 0, 那么|.
③ 如果|, |, 那么对任意, ∈ ℤ, 有| + .
④ 如果|, |, 那么 = 或 = −.
= 251649
16
课堂练习
计算: 将237894与251649都转换为二进制.
解: 其八进制表示分别为(720506) 8与(753401)8
易知对八进制0 − 7有如下二进制转换
0 −> 000 1 −> 001 2 −> 010 3 −> 011
4 −> 100 5 −> 101 6 −> 110 7 −> 111
因此, (720506) 8 = (111010000101000110) 2
(753401) 8 = (111101011100000001) 2
17
总结
自然数或者正整数指的是数1, 2,…, 而整数指的是数
0,±1,±2,⋯. 全体整数的集合记为ℤ, 而全体正整数或
除法:
66 = 2 × 33 + 0 (低位)
33 = 2 × 16 + 1
16 = 2 × 8 + 0
8=2×4+0
4=2×2+0
2=2×1+0
1 = 2 × 0 + 1 (高位)
按从低位到高位顺序, 依次取出上述除法中的余数, 得到
(66)10 = (1000010)2.
12
余数的定义
定义1.1.2 带余除法 = + 中的为用除得出
② 如果|, ≠ 0, 那么|.
③ 如果|, |, 那么对任意, ∈ ℤ, 有| + .
④ 如果|, |, 那么 = 或 = −.
初等数论
3 同余
性质：同余关系是等价关系。 模m等价类: 在模m同余关系下的等价类. [a]m, 简记作[a]。 Zm: Z在模m同余关系下的商集。 在Zm上定义加法和乘法如下: a, b, [a]+[b]=[a+b], [a]· [b]=[ab]. 例6：写出Z4的全部元素以及Z4上的加法表和乘法表. 解 Z4={[0],[1],[2],[3]}, 其中[i]={4k+i |k∈Z}, i=0,1,2,3. + [0] [1] [2] [3] [0] [1] [2] [3] [0] [1] [2] [3] [1] [2] [3] [0] [2] [3] [0] [1] [3] [0] [1] [2] · [0] [1] [2] [3] [0] [0] [0] [0] [0] [1] [0] [1] [2] [3] [2] [0] [2] [0] [2] [3] [0] [3] [2] [1]
解 150=2×3×52, 168=23×3×7. gcd(150,168)=21×31×50×70=6, lcm(150,168)=23×31×52×71=4200.
欧几里得算法-辗转相除法
除法算法: a=qb+r, 0≤r <|b|, 记余数r=a mod b
例如, 20 mod 6=2, 13 mod 4=3, 10 mod 2=0
RSA公钥密码
私钥密码:加密密钥和解密密钥都必须严格保密 公钥密码 (W.Diffie,M.Hellman,1976 ):加密密钥公开,解密 密钥保密
整数. 则 min( rk , sk ) min( r1 , s1 ) min( r2 , s2 ) gcd(a,b)= p1 p2 pk ,
max( rk , sk ) max( r1 , s1 ) max( r2 , s2 ) p p p lcm(a,b)= 1 2 k
初等数论 高等数论
1111
数论是一门研究整数性质的数学分支，它包括了初等数论和高等数论两个方面。
初等数论主要研究整数的基本性质，如整除性、质数、合数、最大公约数、最小公倍数等。
这些概念和性质在小学和初中的数学课程中就已经涉及到了，因此也被称为“小学数论”或“初中数论”。
初等数论的研究方法主要是通过观察、归纳和证明来得出结论，它的研究对象比较具体，结论也比较直观。
高等数论则是在初等数论的基础上，进一步深入研究整数的性质和结构。
它涉及到的概念和方法更加抽象和复杂，如素数分布、数的几何、代数数论、解析数论等。
高等数论的研究需要运用到高等数学的知识和方法，如微积分、线性代数、抽象代数等。
高等数论的研究成果不仅在数学领域有着广泛的应用，而且在计算机科学、物理学、密码学等领域也有着重要的应用。
总的来说，初等数论是高等数论的基础，高等数论则是初等数论的延伸和深化。
无论是初等数论还是高等数论，它们都是数学中非常重要的分支，对于我们深入理解整数的性质和结构、推动数学的发展都有着重要的意义。
初等数论简介
初等数论初等数论是研究整数最基本性质的一个数学分支，它也是数学中最古老的分支之一，至今仍有许多没有解决的问题。
初等数论是数学中“理论与实践”相结合最完美的基础课程。
近代数学中许多重要思想、概念、方法与技巧都是对整数性质的深入研究而不断丰富和发展起来的。
近几十年来，初等数论在计算机科学、组合数学、代数编码、信号的数字处理等领域内得到广泛的应用。
在日常生活中，也常会遇到一些数论问题。
具体内容1．整数的可除性：了解整除的概念，掌握带余数除法及其运用；理解最大公因数的基本概念及其性质，掌握用辗转相除法求整数的最大公因数。
掌握整除的性质及其运用，会求整数的最小公倍数。
掌握两个整数的最小公倍数与最小公因数的关系。
了解质数基本概念与性质，理解算术基本定理及其证明，会运用算术基本定理解决问题。
了解函数[x]，{x}的基本性质，运用这两个函数解决n!的标准分解式。
2．不定方程：掌握二元及多元一次不定方程有解的充要条件，熟练掌握一次不定方程的求解。
勾股数公式的推导及其运用，了解费尔马问题及无穷递降法。
3．同余：理解同余的概念及其基本性质，掌握检查因数的一些方法和弃九法。
了解剩余类及完全剩余系的性质，并会加以运用。
了解简化剩余系及其性质，会推导欧拉函数，知道它的简单运用。
应用简化剩余系的性质证明Euler定理和Fermat定理，运用欧拉定理研究循环小数；欧拉定理与费马定理的综合运用。
了解同余在信息安全与密码中的运用。
4．同余式：了解同余式的基本概念，掌握一次同余式的求解；理解孙子定理，会解模互素的一次同余式组的求解。
了解一般一次同余式组的解法，掌握高次同余式的解数及解法。
理解质数模的同余式解数的有关定理，并予初步运用。
5.连分数：掌握连分数的基本性质、把实数表成连分数和循环连分数，了解连分数在天文中的运用。
初等数论是数论的一个分支。
它以算术方法为主要的研究方法，而区别于数论的其他分支。
公元前6世纪,古希腊数学家毕达哥拉斯就已研究过整数的可除性问题，例如，当时已经知道正整数中有奇数、偶数、素数、复合数等各种类型的数。
初等数论
序言数论是研究整数性质的一门很古老的数学分支，其初等部分是以整数的整除性为中心的，包括整除性、不定方程、同余式、连分数、素数（即整数）分布以及数论函数等内容，统称初等数论（Elementary Number Theory）。
初等数论的大部份内容早在古希腊欧几里德的《几何原本》中就已出现。
欧几里得证明了素数有无穷多个，他还给出求两个自然数的最大公约数的方法，即所谓欧几里得算法。
我国古代在数论方面亦有杰出之贡献，现在一般数论书中的“中国剩余定理”正是我国古代《孙子算经》中的下卷第26题，我国称之为“孙子定理”。
近代初等数论的发展得益于费马、欧拉、拉格朗日、勒让德和高斯等人的工作。
1801年，高斯的《算术探究》是数论的划时代杰作。
“数学是科学之王，数论是数学之王”。
-----高斯由于自20世纪以来引进了抽象数学和高等分析的巧妙工具，数论得到进一步的发展，从而开阔了新的研究领域，出现了代数数论、解析数论、几何数论等新分支。
而且近年来初等数论在计算器科学、组合数学、密码学、代数编码、计算方法等领域内更得到了广泛的应用，无疑同时间促进着数论的发展。
数论是以严格和简洁著称，内容既丰富又深刻。
我将会介绍数论中最基本的概念和理论，希望大家能对这门学问产生兴趣，并且对中小学时代学习过的一些基本概念，例如整除性、最大公因子、最小公倍数、辗转相除法等，有较深入的了解。
第一章整数的整除性§1.1整除的概念一、基本概念1、自然数、整数2、正整数、负整数3、奇数、偶数一个性质：整数+整数=整数整数-整数=整数整数*整数=整数二、整除1、定义：设a，b是整数，b≠0。
如果存在一个整数q使得等式：a=bq成立，则称b能整除a或a能被b整除，记作b∣a；如果这样的q不存在，则称b不能整除a。
2、整除的性质（1）如果b∣a，c∣b，则c∣a.（2）如果b∣a，则cb∣ca.（3）如果c∣a，则对任何整数d，c∣da.（4）如果c∣a，c∣b，则对任意整数m，n，有c∣ma+nb.（5）如果a∣b，b∣a，则a=±b.3、质数、合数质数（素数）是指在大于1的自然数中，除了1和它本身外，不能被其他自然数整除（除0以外）的数称之为素数（质数）。
初等数论的性质与定理总结
初等数论的性质与定理总结初等数论是数论中的一个基础分支，研究整数的性质和整数运算规律。
本文将总结初等数论中的一些重要性质与定理。
一、整数的整除性质1. 整数的除法基本性质：对于任意整数a、b和非零整数c，存在唯一的整数q使得a = bq + c。
2. 整除关系的传递性：如果a能整除b，且b能整除c，则a能整除c。
3. 整除关系的辗转相除法：对于任意整数a和非零整数b，存在唯一的整数q和r使得a = bq + r（其中0 ≤ r < |b|）。
二、质数与合数1. 质数的定义：质数是指大于1且只能被1和自身整除的整数。
例如，2、3、5、7等都是质数。
2. 质因数分解定理：每个大于1的整数都可以唯一地表示为若干个质数的乘积。
3. 最大公约数与最小公倍数的性质：对于任意整数a和b，记a和b 的最大公约数为gcd(a, b)，最小公倍数为lcm(a, b)，则有以下性质： - gcd(a, b) = gcd(b, a)- gcd(a, 0) = |a|- lcm(a, b) = |ab| / gcd(a, b)三、模运算与同余1. 模运算的基本性质：对于任意整数a、b和正整数n，有以下性质：- (a + b) mod n = (a mod n + b mod n) mod n- (a - b) mod n = (a mod n - b mod n) mod n- (a * b) mod n = (a mod n * b mod n) mod n2. 同余关系的性质：对于任意整数a、b和正整数n，如果a与b模n同余（记作a ≡ b (mod n)），则有以下性质：- a + c ≡ b + c (mod n)- ac ≡ bc (mod n)- 如果a ≡ b (mod n)，则a^k ≡ b^k (mod n)对于任意正整数k四、费马小定理与欧拉定理1. 费马小定理：如果p是质数，a是任意正整数且p不整除a，则有a^(p-1) ≡ 1 (mod p)。
(0346)《初等数论》网上作业题及答案
（0346）《初等数论》网上作业题及答案1：第一次作业2：第二次作业3：第三次作业4：第四次作业5：第五次作业1：[论述题]数论第一次作业参考答案：数论第一次作业答案2：[单选题]如果a|b，b|c，则（）。
A：a=cB：a=-cC：a|cD：c|a参考答案：C马克思主义哲学是我们时代的思想智慧。
作为时代的思想智慧，马克思主义哲学主要具有反思功能、概括功能、批判功能和预测功能。
（1）“反思”是哲学思维的基本特征，是以思想的本身为内容，力求思想自觉其为思想。
通过不断的反思，揭示自己时代的本质和规律，达到对事物本质和规律性的认识。
（2）概括是马克思主义哲学的重要功能，是马克思主义哲学把握人与世界总体性关系的基本思维方式。
（3）马克思主义哲学的批判功能主要是指对现存世界的积极否定。
（4）马克思主义哲学的预测功能在于预见现存世界的发展趋势。
3：[单选题]360与200的最大公约数是（）。
A：10B：20C：30D：40参考答案：D数论第一次作业答案4：[单选题]如果a|b，b|a ，则（）。
A：a=bB：a=-bC：a=b或a=-bD：a，b的关系无法确定参考答案：C数论第一次作业答案5：[单选题]-4除-39的余数是（）。
A：3B：2C：1D：0参考答案：C数论第一次作业答案6：[单选题]设n，m为整数，如果3整除n，3整除m，则9（）mn。
A：整除B：不整除C：等于D：小于参考答案：A数论第一次作业答案7：[单选题]整数6的正约数的个数是（）。
A：1B：2C：3D：4参考答案：D数论第一次作业答案8：[单选题]如果5|n ，7|n，则35（）n 。
A：不整除B：等于C：不一定D：整除参考答案：D数论第一次作业答案1：[论述题]数论第二次作业参考答案：数论第二次作业答案2：[单选题]288与158的最大公约数是（）。
A：2B：4C：6D：8参考答案：A数论第二次作业答案3：[单选题]-337被4除余数是（）。
初等数论知识点总结
初等数论知识点总结初等数论是数论中的一个分支，它主要研究自然数的整除性质以及其它基本性质。
初等数论主要包括素数与合数、整数表示、整数方程、模运算、同余方程、数乘次幂循环节等内容。
下面将对初等数论的关键知识点进行总结。
1.素数与合数：素数（质数）是只能被1和自身整除的自然数，合数是除了1和自身以外还能被其它数整除的自然数。
质数有无穷多个，这个结论由欧几里得证明。
常见的质数有2、3、5、7等。
2.素因子分解：任何一个自然数都可以唯一分解成若干个素数的乘积形式，这个分解过程称为素因子分解。
例如，24可以分解为2^3*3，其中2和3是24的素因子。
3.最大公约数与最小公倍数：最大公约数（GCD）是指两个或多个数中最大的能够整除所有这些数的自然数，最小公倍数（LCM）是指两个或多个数中最小的能够被这些数整除的自然数。
GCD可以通过欧几里得算法进行计算，而LCM可以通过两个数的乘积除以它们的GCD得到。
4.模运算与同余方程：模运算是将一个数除以另一个数所得到的余数，同余方程是指具有相同余数的整数关系。
例如，如果a除以n与b除以n得到相同的余数，即a≡b (mod n)，则称a与b在模n下是同余的。
5.素数定理与欧拉定理：素数定理是指当自然数x趋于无穷大时，小于等于x的素数的数量约等于x / ln(x)，其中ln(x)是自然对数。
欧拉定理是指当正整数a与自然数n互质时，a^(φ(n)) ≡ 1 (mod n)，其中φ(n)是小于n且与n互质的自然数的个数。
6.立方与四方数：立方数是指一个数的立方，四方数是指一个数可以表示为四个整数的平方和。
高斯数学说是指四方数的性质，它由高斯证明，表示为四个整数的平方和的非负整数解的个数等于该数的除以8的余数。
7.费马小定理与小费马定理：费马小定理是费马定理的一个特殊情况，它表明如果p是一个素数，a是一个与p互质的整数，那么a^(p-1) ≡ 1 (mod p)。
小费马定理是费马小定理的推广，它表明如果a是一个整数，m是一个大于1的自然数，且a与m互质，那么a^φ(m) ≡ 1 (mod m)，其中φ(m)是小于m且与m 互质的自然数的个数。
初等数论作业答案
初等数论1：[单选题]已知361a是一个4位数（其中a是个位数），它能被5整除，也能被3整除，则a的值是（）。
A：0B：2C：5D：9参考答案：C2：[单选题]下面的（）是模4的一个简化剩余系。
A：4,17B：1,15C：3,23D：13,6参考答案：B3：[单选题]小于20的正素数的个数是（）。
A：11B：10C：9D：8参考答案：D 4：[单选题]下面的数是3的倍数的数是（）。
A：19B：119C：1119D：11119参考答案：C5：[单选题]-4除-39的余数是（）。
A：3B：2C：1D：0参考答案：C6：[单选题]一个正整数n的各位上的数字是0或1，并且n能被2和3整除，则最小的n 是（）。
A：1110B：1101C：1011D：1001参考答案：A7：[单选题][[4.5]+[3.7]]等于（）。
A：3B：4C：7D：8参考答案：C8：[单选题]{{1.8}+{2.9}}等于（）。
A：0.4B：0.5C：0.6D：0.7参考答案：D 9：[单选题]100与44的最小公倍数是（）。
A：4400B：2200C：1100D：440参考答案：C10：[单选题]使3的n次方对模7同余于1的最小的正整数n等于（）。
A：6B：2C：3D：13参考答案：A11：[单选题]设a,b,c,d是模5的一个简化剩余系，则a+b+c+d对模5同余于（）。
A：0B：1C：2D：3参考答案：A12：[单选题]下面的（）是不定方程3x + 7y = 20的一个整数解。
A：x=0,y=3B：x=2,y=1C：x=4,y=2D：x=2,y=2参考答案：D13：[单选题]下面的（）是模4的一个完全剩余系。
A：9，17，-5，-1B：25，27，13，-1C：0，1，6，7D：1，-1，2，-2参考答案：C14：[单选题]下面的（）是模12的一个简化剩余系。
A：0，1，5，11B：25，27，13，-1C：1，5，7，11D：1，-1，2，-2参考答案：C15：[单选题]若a，b均为偶数，则a + b为（）。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
备注：纯手写代码，注释。
数论1、素数（1）暴力求解法根据素数的概念，没有1和其本身没有其他正因数的数。
所以只需枚举比这个数小的数，看能整除即可；C++代码：#include<iostream>#include<cstdio>#include<cmath>using namespace std;bool determine(int number){if(n<=2)return false;if(!n%2)return false;for(int i=3;i<=ceil(sqrt(number));i+=2)//去掉了偶数的判断，效率提高一倍/*如果number整除以i，那么会得到两个的因数，而较小的那个因数不会超过number的二分之一次方；所以只需判断到number的平方根向上取整即可；*/if(number%i);else return false;return true;}int main(){int sum;cin>>sum;if(determine(sum))cout<<"YES!";else cout<<"NO!";return 0;}时间复杂度：o(sqrt(n)/2);空间复杂度：几乎没有；（2）一般线性筛法：因为任何一个合数都能分解成几个素数相乘的形式；所以可以做一个表，首先把2设为质数，然后将2的倍数设为合数，剩下的数就是新得到的质数，然后重复这个过程，直到筛到合适的范围即可；但是这个算法有缺陷：1、同一个数可能被筛多次，这就产生了多余的步骤。
2、占用空间很大，如果使用bool数组的话，只能筛到1e9；3、从1-n筛，不能从m-n开始筛；C++代码：#include<cstring>#include<cmath>#include<iostream>using namespace std;bool s[1000000000];int m,n;int main(){cin>>m>>n;memset(s,true,n);s[0]=s[1]=0;//输出M—N之间所有素数；for(int i=2;i<=ceil(sqrt(n));++i)if(s[i]){for(int j=i;j<=n;++j)if(s[i*j])s[i*j]=false;}for(int i=m;i<=n;++i)if(s[i])cout<<i<<' ';return 0;}时间复杂度：o(n*loglogn);空间复杂度：很大！注意数据大的话可能会爆空间；（3）线性筛法求素数这个占空间就更大了，需要使用一个bool数组和int数组而亲身试验得到int数组最多开到1e8……很无语，快确实是快了，但是测试数据一大，爆空间就更容易了；#include<iostream>#include<cstdio>#include<cmath>using namespace std;int m,n,sum;bool inp[1000000000];int s[100000000]={0,0};int main(){cin>>m>>n;for(int i=2;i<=n;++i){if(!inp[i])s[sum++]=i;for(int j=0;j<sum&&i*s[j]<=n;++j){inp[i*s[j]]=true;if(!(i*s[j]))break;}}for(int i=m;i<=n;++i)if(!inp[i])cout<<i<<' ';return 0;}2、唯一分解定理任何数都可以被唯一的分解成多个素数之积例如：456=2*2*2*3*19；C++代码：#include<cstring>#include<cmath>#include<iostream>#include<algorithm>#include<cstdlib>using namespace std;bool s[1000000];int m,n,sum=0,num;int Prime[1212121];int zhi[1500];void Primes(){for(int i=1;i<=num;++i)s[i]=true;s[0]=s[1]=0;for(int i=2;i<=num;++i)if(s[i]){Prime[++sum]=i;for(int j=i;j<=num;++j)if(s[i*j])s[i*j]=false;}}int main(){int flag=0;cin>>num;int number=num;Primes();if(s[num]){cout<<num<<'='<<num;return 0;}cout<<num<<"=";str.chu();while(num>1)for(int i=1;num>1&&i<=sum;++i) if(!(num%Prime[i])){zhi[++flag]=Prime[i];num/=Prime[i];}sort(zhi+1,zhi+flag+1);cout<<zhi[1];for(int i=2;i<=flag;++i)cout<<"*"<<zhi[i];return 0;}首先做一个质数表，并把质数存到数组里，然后用数模每个素数，如果为0则记录素数，最后排个序输出；4、欧拉函数欧拉函数φ（n）为不大于n的与n互素的数的个数；A与B互素，表示a与b的最大公约数为1，即（a，b）=1；欧拉函数的符号φ读作fhi，在搜狗的特殊符号里可以找到；，其中pi为x的质因数，其中φ(1)=1（唯一与1互质的数是1本身）设n为正整数，以φ(n)表示不超过n且与n互素的正整数的个数，称为n的欧拉函数值φ：N→N，n→φ(n)称为欧拉函数。
几个性质（来自百度百科）1、若n是质数p的k次幂，，因为除了p的倍数外，其他数都跟n互质。
2、欧拉函数是积性函数——若m,n互质，3、特殊性质：当n为奇数时， , 证明与上述类似。
4、若n为质数则5、设p是素数，a是一个正整数，那么C++实现：#include<cstring>#include<cmath>#include<iostream>#include<algorithm>#include<cstdlib>using namespace std;bool s[1000000];int m,n,sum=0,num;int Prime[1212121];int zhi[1500];bool asd[1500];int phi(int n){int i,rea=n;for(i=2;i*i<=n;i++){if(n%i==0){rea=rea-rea/i;while(n%i==0) n/=i;}}if(n>1)rea=rea-rea/n;return rea;}void Primes(){for(int i=1;i<=num;++i)s[i]=true;s[0]=s[1]=0;for(int i=2;i<=num;++i)if(s[i]){Prime[++sum]=i;for(int j=i;j<=num;++j)if(s[i*j])s[i*j]=false;}}int main(){int flag=0;cin>>num;int number=num;Primes();if(num==1||!num){cout<<"fhi"<<'('<<number<<")=";cout<<num;return 0;}if(s[num]){cout<<"fhi"<<'('<<number<<")="<<number-1;return 0;}while(num>1)for(int i=1;num>1&&i<=sum;++i)if(!(num%Prime[i])){zhi[++flag]=Prime[i];num/=Prime[i];}int fenzi=1,fenmu=1;sort(zhi+1,zhi+flag+1);for(int i=1;i<=flag;++i)if(!asd[zhi[i]]){asd[zhi[i]]=true;fenzi*=zhi[i]-1;fenmu*=zhi[i];}cout<<"fhi("<<number<<")="<<number/fenmu*fenzi;//cout<<"fhi("<<number<<")="<<fhi(number);/*这是另一种求欧拉函数值的方法*/return 0;}5、欧几里得算法辗转相除法，根据公式(a,b)=(b,r)其中r为a%b，即a/b；C++代码：（1）递归#include<iostream>#include<cstdio>using namespace std;int GCD(int a,int b){if(a%b)return GCD(b,a%b);else return b;}int main(){int a,b;cin>>a>>b;cout<<GCD(a,b);return 0;}（2）递推#include<iostream>using namespace std;int main(){int a,b,r;cin>>a>>b;r=m%n;while(r!=0){a=b;b=r;r=m%n;}cout<<n;return 0;}6、扩展欧几里得扩展欧几里得又称斐蜀定理，对于不完全为0 的非负整数a，b，gcd（a，b）表示a，b 的最大公约数，必然存在整数对x，y ，使得gcd（a，b）=ax+by；求同余方程#include<cstdio>void exgcb(int a,int b,int &x,int &y){if(!b){x=1;y=0;return;int q=a/b;int r=a%b;exgcb(b,r,y,x);y-=q*x;}int main(){int x,y;int a,b;scanf("%d %d",&a,&b);exgcb(a,b,x,y);while(x<0)x+=b;printf("%d",x);return 0;}求乘法逆元#include<cstdio>void exgcb(int a,int b,int &x,int &y) {if(!b)x=1;y=0;return;}int q=a/b;int r=a%b;exgcb(b,r,y,x);y-=q*x;}int Multiplicative inverse(int a,int b) {int x,y;int gcb=GCD(a,b,x,y);if(1%gcb)return -1;x*=1%gcb;b=abs(b);int answer=x%b;while(answer<=0)answer+=b;return answer;}int main(){int x,y;int a,b;scanf("%d %d",&a,&b);exgcb(a,b,x,y);while(x<0)x+=b;printf("%d\n",x);cout<<Multiplicative inverse(a,b);return 0;}求线性方程ax+by=c这个方程等同于ax≡c（mod b）所以（此文档部分内容来源于网络，如有侵权请告知删除，文档可自行编辑修改内容，供参考，感谢您的配合和支持）。