初等数论课件：同余理论及其应用

《初等数论》

同余理论及其应用

2.1

同余的定义

由同余的定义可以得到以下两个同余关系成立的充分必要条件:

2.2

同余概念的基本性质

由同余的性质可得到以下两个很重要的结论：

同余的性质的应用一、检查因数：引理1一个整数能被3（或9）整除的充要条件是它的十进位数码的和能被3（或9）整除.（只需考虑正整数即可）

思考：1、判断一个整数是否能被11整除还有没有别的方法？（两种）2、类似的，试着给出判断一个整数是否能被37或101整除的充要条件.

结论：弃九法只能用来检验计算结果是否是错的，但是并不能保证计算的正确性。

作业：P381，2，3，4《初等数论》

2.1

同余的定义

由同余的定义可以得到以下两个同余关系成立的充分必要条件:

2.2

同余概念的基本性质

由同余的性质可得到以下两个很重要的结论：

《初等数论》

2.3

剩余类与剩余系

《初等数论》

2.4

几个重要的定理

欧拉(Euler)定理、费马(Fermat)小定理、威尔逊(Wilson)定理，以及2.6节介绍的拉格朗日(Lagrange)定理是数论中的几个重要定理，它们在数论中有着广泛的应用.

证明：

证明：

Euler定理与Fermat定理的应用：

证明：

但由欧拉判别法知以上同余式无解，导致矛盾，故命题成立.证毕.

注：上述定理是欧拉定理与费马小定理在循环小数中的一个应用.作业：P42:3,4《初等数论》

2.5

同余式的概念及同余式的解

2.5.1

一次同余式的解

一次同余式的几种解法

(假设同余式均有解).

Ⅳ.利用辗转相除法消去的系数.

Ⅳ.

利用不定方程求一次同余式的解.

同余式(5)的模小于同余式(2)的模.将这一步骤继续下去，使问题归结为求解一个模很小且能直接求出其解的同余式.再将以上步骤反演回去就可求出同余式的全部解.

Ⅶ.利用矩阵的初等变换求一次同余式的解.下面将给出利用矩阵初等变换解一次同余式的方法，该方法简单易于运算，分为以下两种情形讨论：

2.5.2

中国剩余定理与一次同余式组的解法

《初等数论》

在代数里面，我们需要解决代数方程的求解问题。在数论里面也有与解代数方程类似的问题：求同余式方程的解。

4.1同余式的概念及同余式的解

4.1

一次同余式的解

一次同余式的几种解法

(假设同余式均有解).

Ⅳ.利用辗转相除法消去的系数.

Ⅳ.利用不定方程求一次同余式的解.

同余式(5)的模小于同余式(2)的模.将这一步骤继续下去，使问题归结为求解一个模很小且能直接求出其解的同余式.再将以上步骤反演回去就可求出同余式的全部解.

Ⅶ.利用矩阵的初等变换求一次同余式的解.

下面将给出利用矩阵初等变换解一次同余式的方法，该方法简单易于运算，分为以下两种情形讨论：

4.2孙子定理（中国剩余大定理）

古代《孙子算经》：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”“答曰二十三”。

《初等数论》

2.6

高次同余式及质数模的同余式的初步解法

注:目前还没有一个一般的方法去解高次同余式和质数模的同余式，上面的方法仅仅是先把合数模的同余式化成质数幂模的同余式，然后再讨论质数幂模的同余式的解法.

注:上述定理也给出了此类同余式的一个解法，用下面的例题来详细说明此定理

注：以上把解高次同余式归结到了解质数模的高次同余式，由于还没有解质数模的同余式的一般方法，只能就质数模同余式的次数与解数的关系做初步讨论.

《初等数论》

2.7

二次剩余及二次同余式的解法

2.7.1

奇质数模的二次剩余与二次非剩余