对于互质的整数a和n,有a^φ(n) ≡ 1 (mod n) 证明: 首先证明下面这个命题: 对于集合Zn={x1,x2,...,xφ(n)},其中xi(i=1,2,…φ(n))是φ(n)个n的素数,且两两互素,即n的一个化简剩余系,或称简系,或称缩系),考虑集合S = {a*x1(mod n),a*x2(mod n),...,a*xφ(n)(mod n)} 则S = Zn 1) 由于a,n互质,xi也与n互质,则a*xi也一定于p互质,因此 任意xi,a*xi(mod n) 必然是Zn的一个元素 2) 对于Zn中两个元素xi和xj,如果xi ≠ xj 则a*xi(mod n) ≠ a*xi(mod n),这个由a、p互质和消去律可以得出。 所以,很明显,S=Zn 既然这样,那么 (a*x1 × a*x2×...×a*xφ(n))(mod n) = (a*x1(mod n) × a*x2(mod n) × ... × a*xφ(n)(mod n))(mod n) = (x1 × x2 × ... × xφ(n))(mod n) 考虑上面等式左边和右边 左边等于(a*(x1 × x2 × ... × xφ(n))) (mod n) 右边等于x1 × x2 × ... × xφ(n))(mod n) 而x1 × x2 × ... × xφ(n)(mod n)和n互质 根据消去律,可以从等式两边约去,就得到: a^φ(n) ≡ 1 (mod n) 推论:对于互质的数a、n,满足a^(φ(n)+1) ≡ a (mod n) 费马定理: a是不能被质数p整除的正整数,则有a^(p-1) ≡ 1 (mod p) 证明这个定理非常简单,由于φ(p) = p-1,代入欧拉定理即可证明。 同样有推论:对于不能被质数p整除的正整数a,有a^p ≡ a (mod p)欧拉公式 简单多面体的顶点数V、面数F及棱数E间有关系 V+F-E=2 这个公式叫欧拉公式。公式描述了简单多面体顶点数、面数、棱数特有的规律。 在数学历史上有很多公式都是欧拉(Leonhard Euler 公元1707-1783年)发现的,它们都叫做欧拉公式,它们分散在各个数学分支之中。 1、复变函数论里的欧拉公式: e^ix=cosx+isinx,e是自然对数的底,i是虚数单位。 它将三角函数的定义域扩大到复数,建立了三角函数和指数函数的关系,它在复变函数论里占有非常重要的地位。 将公式里的x换成-x,得到: e^-ix=cosx-isinx,然后采用两式相加减的方法得到: sinx=(e^ix-e^-ix)/(2i),cosx=(e^ix+e^-ix)/2. 这两个也叫做欧拉公式。将e^ix=cosx+isinx中的x取作∏就得到: e^i∏+1=0. 这个恒等式也叫做欧拉公式,它是数学里最令人着迷的一个公式,它将数学里最重要的几个数学联系到了一起:两个超越数:自然对数的底e,圆周率∏,两个单位:虚数单位i和自然数的单位1,以及数学里常见的0。数学家们评价它是“上帝创造的公式”,我们只能看它而不能理解它。 2、拓扑学里的欧拉公式: V+F-E=X(P),V是多面体P的顶点个数,F是多面体P的面数,E是多面体P的棱的条数,X(P)是多面体P的欧拉示性数。 如果P可以同胚于一个球面(可以通俗地理解为能吹胀成一个球面),那么X(P)=2,如果P同胚于一个接有h个环柄的球面,那么X(P)=2-2h。 X(P)叫做P的拓扑不变量,是拓扑学研究的范围。 3、初等数论里的欧拉公式: 欧拉φ函数:φ(n)是所有小于n的正整数里,和n互素的整数的个数。n是一个正整数。 欧拉证明了下面这个式子: 如果n的标准素因子分解式是p1^a1*p2^a2*……*pm*am,其中众pj(j=1,2,……,m)都是素数,而且两两不等。则有 φ(n)=n(1-1/p1)(1-1/p2)……(1-1/pm) 利用容斥原理可以证明它。 定理:正整数a与n互质,则a^φ(n)除以n余1 证明:设集合{A1,A2,...,Am}为模n的一个缩系(若整数A1,A2,...,Am模n分别对应0,1,2,...,n-1中所有m个与n互素的自然数,则称集合{A1,A2,...,Am}为模n的一个缩系) 则{a A1,a A2,...,a Am}也是模n的一个缩系(如果a Ax与a Ay (x不等于y)除以n余数相同,则a(Ax-Ay)是n的倍数,这显然不可能) 即A1*A2*A3*……Am≡aA1*aA2*……aAm(mod n) (这里m=φ(n)) 两边约去A1*A2*A3*……Am即得1≡a^φ(n)(mod n)来自百度百科