初等數(shù)論課件：同余理論及其應(yīng)用

《初等數(shù)論》

同余理論及其應(yīng)用

2.1

同余的定義

由同余的定義可以得到以下兩個(gè)同余關(guān)系成立的充分必要條件:

2.2

同余概念的基本性質(zhì)

由同余的性質(zhì)可得到以下兩個(gè)很重要的結(jié)論：

同余的性質(zhì)的應(yīng)用一、檢查因數(shù)：引理1一個(gè)整數(shù)能被3（或9）整除的充要條件是它的十進(jìn)位數(shù)碼的和能被3（或9）整除.（只需考慮正整數(shù)即可）

思考：1、判斷一個(gè)整數(shù)是否能被11整除還有沒(méi)有別的方法？（兩種）2、類(lèi)似的，試著給出判斷一個(gè)整數(shù)是否能被37或101整除的充要條件.

結(jié)論：棄九法只能用來(lái)檢驗(yàn)計(jì)算結(jié)果是否是錯(cuò)的，但是并不能保證計(jì)算的正確性。

作業(yè)：P381，2，3，4《初等數(shù)論》

2.1

同余的定義

由同余的定義可以得到以下兩個(gè)同余關(guān)系成立的充分必要條件:

2.2

同余概念的基本性質(zhì)

由同余的性質(zhì)可得到以下兩個(gè)很重要的結(jié)論：

《初等數(shù)論》

2.3

剩余類(lèi)與剩余系

《初等數(shù)論》

2.4

幾個(gè)重要的定理

歐拉(Euler)定理、費(fèi)馬(Fermat)小定理、威爾遜(Wilson)定理，以及2.6節(jié)介紹的拉格朗日(Lagrange)定理是數(shù)論中的幾個(gè)重要定理，它們?cè)跀?shù)論中有著廣泛的應(yīng)用.

證明：

證明：

Euler定理與Fermat定理的應(yīng)用：

證明：

但由歐拉判別法知以上同余式無(wú)解，導(dǎo)致矛盾，故命題成立.證畢.

注：上述定理是歐拉定理與費(fèi)馬小定理在循環(huán)小數(shù)中的一個(gè)應(yīng)用.作業(yè)：P42:3,4《初等數(shù)論》

2.5

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

2.5.1

一次同余式的解

一次同余式的幾種解法

(假設(shè)同余式均有解).

Ⅳ.利用輾轉(zhuǎn)相除法消去的系數(shù).

Ⅳ.

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

同余式(5)的模小于同余式(2)的模.將這一步驟繼續(xù)下去，使問(wèn)題歸結(jié)為求解一個(gè)模很小且能直接求出其解的同余式.再將以上步驟反演回去就可求出同余式的全部解.

Ⅶ.利用矩陣的初等變換求一次同余式的解.下面將給出利用矩陣初等變換解一次同余式的方法，該方法簡(jiǎn)單易于運(yùn)算，分為以下兩種情形討論：

2.5.2

中國(guó)剩余定理與一次同余式組的解法

《初等數(shù)論》

在代數(shù)里面，我們需要解決代數(shù)方程的求解問(wèn)題。在數(shù)論里面也有與解代數(shù)方程類(lèi)似的問(wèn)題：求同余式方程的解。

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

4.1

一次同余式的解

一次同余式的幾種解法

(假設(shè)同余式均有解).

Ⅳ.利用輾轉(zhuǎn)相除法消去的系數(shù).

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

同余式(5)的模小于同余式(2)的模.將這一步驟繼續(xù)下去，使問(wèn)題歸結(jié)為求解一個(gè)模很小且能直接求出其解的同余式.再將以上步驟反演回去就可求出同余式的全部解.

Ⅶ.利用矩陣的初等變換求一次同余式的解.

下面將給出利用矩陣初等變換解一次同余式的方法，該方法簡(jiǎn)單易于運(yùn)算，分為以下兩種情形討論：

4.2孫子定理（中國(guó)剩余大定理）

古代《孫子算經(jīng)》：“今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問(wèn)物幾何？”“答曰二十三”。

《初等數(shù)論》

2.6

高次同余式及質(zhì)數(shù)模的同余式的初步解法

注:目前還沒(méi)有一個(gè)一般的方法去解高次同余式和質(zhì)數(shù)模的同余式，上面的方法僅僅是先把合數(shù)模的同余式化成質(zhì)數(shù)冪模的同余式，然后再討論質(zhì)數(shù)冪模的同余式的解法.

注:上述定理也給出了此類(lèi)同余式的一個(gè)解法，用下面的例題來(lái)詳細(xì)說(shuō)明此定理

注：以上把解高次同余式歸結(jié)到了解質(zhì)數(shù)模的高次同余式，由于還沒(méi)有解質(zhì)數(shù)模的同余式的一般方法，只能就質(zhì)數(shù)模同余式的次數(shù)與解數(shù)的關(guān)系做初步討論.

《初等數(shù)論》

2.7

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

2.7.1

奇質(zhì)數(shù)模的二次剩余與二次非剩余