Question

设m是大于1的正+整数.+(i)如果a是与m互素的整数,则a、2a、…、ma+是否构成模m的完全剩余系？为什么？(ii)证明:当a=b(modm)且<m时，必有a=b

Answer 1

问：设m是大于1的正+整数.+(i)如果a是与m互素的整数,则a、2a、…、ma+是否构成模m的完全剩余系？为什么？(ii)证明:当a=b(modm)且

答：设m是大于1的正整数，a是与m互素的正整数，则使得ae=1( mod m)成立的最小正整数e叫做a对模m的指数，记作ordm(a)。如果a对模m的指数是m的欧拉函数值

问：设ψ(n)是Euler函数.(i)求ψ(14630).(ii)证明:当正整数a、b适合a(b)

答：记作φ(n) 。欧拉函数的通式：φ(n)=n*(1-1/p1)(1-1/p2)(1-1/p3)*(1-1/p4)……(1-1/pn)其中p1, p2……pn为n的所有质因数，n是不为0的整数。φ(1)=1.