第一讲阶与原根本讲概述阶也常被称为指数。设是一个固定的整数，，由欧拉定理可知，，故存在整数，使得，我们将具有这一性质的最小正整数k称为a模m的阶.它具有极其锐利的性质：设，k是a模m的阶，则原根的概念与性质设是一个固定的整数，，且a模m的阶=，则称a为模m的原根。是否对每一个正整数m，模m的原根都存在呢？原根有什么性质呢？为此我们还需要深入的讨论阶的性质。拉格朗日定理设p为素数，考察在模p意义下的一个n次整系数多项式则同余方程在模p的意义下至多有n个不同的根。利用数学归纳法，因式定理，以及同余可证得拉格朗日定理。例题精讲【例1】设a为大于1的正整数，.证明：.【例2】设q为奇素数，q为的素因子。证明：1【例3】设q为费马数的素因子。证明：当时，有.【例4】求所有的正整数n，使得.【例5】设p为素数，证明：存在素数q，使得对任意，都有不整除.以下记a模m的阶为。【例6】（1）设，a,b,(a,m)=(b,m)=1，则.（2）设。则【例7】设p为奇素数，则模p的原根存在。【例8】设p为奇素数，，则模的原根存在。【例9】设p为奇素数，证明：对，都有2这里认为【例10】设p为给定奇素数，成满足下述条件的正整数m为“好数”:(1)m；(2)存在n，使得求“好数”的个数。大显身手练习1.设n为给定的正整数，求最小的正整数m，使得.练习2.设3为奇素数，且p.记集合证明：S中至多有p-1个元素是p的倍数。练习3：设m.证明：若则是一个素数。练习4：求所有的素数组(p,q,r)，使得练习5：设p为素数，证明集合n中存在无穷多个素数。练习6：求所有的素数对，使得3练习7：设n是大于1的奇数，证明：对任意正整数m，都有n不整除.练习8.设p为素数。证明：存在p-1个整数，使得数对模两两不同余。练习9：设p为素数，且求满足：（1）a,b,c,d（2）的数的组数(a,b,c,d)的组数。练习10：斐波那契数列定义如下证明：对任意素数p，数是数列中第一个能被p整除的数的充要条件是：存在模p的原根r，使得(r+1)(r+2)4
