9第九讲 阶与原根 学生版

第九讲 阶与原根

本讲概述

阶也常被称为指数。设m?1是一个固定的整数，(a,m)?1，由欧拉定理可知，

，故存

在整数k(1?k?m)，使得ak?1(modm)，我们将具有这一性质的最小正整数k称为a模m的阶.它具有极其锐利的性质：

设(a,m)?1，k是a模m的阶，则au?1(modm)?k|u

原根的概念与性质

设m?1是一个固定的整数，(a,m)?1，且a模m的阶=

，则称a为模m的原根。

是否对每一个正整数m，模m的原根都存在呢？原根有什么性质呢？为此我们还需要深入的讨论阶的性质。

拉格朗日定理

设p为素数，考察在模p意义下的一个n次整系数多项式

则同余方程

在模p的意义下至多有n个不同的根。

利用数学归纳法，因式定理，以及同余可证得拉格朗日定理。

例题精讲

【例1】设a为大于1的正整数，证明：

【例2】设q为奇素数，q为

的素因子。证明：

.

.

【例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为奇素数，证明：对

，都有

这里认为

【例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：求所有的素数对

练习7：设n是大于1的奇数，证明：对任意正整数m，都有n不整除【提示：考虑n-1所含的2的次幂】

练习8.设p为素数。证明：存在p-1个整数对模

两两不同余。

，使得数

.

，使得

【提示：运用中国剩余定理】

练习9：设p为素数，且（1）a,b,c,d（2）

的数的组数(a,b,c,d)的组数。

练习10：斐波那契数列

定义如下

证明：对任意素数p，数(r+1)(r+2)

是数列

中第一个能被p整除的数的充要条件是：存在模p的原根r，使得

求满足：

【提示：考虑数列中第一个能被p整除的数，再结合反证法找到矛盾】

本文来源：https://www.bwwdw.com/article/wfft.html