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

《初等數(shù)論》

同余理論及其應用

2.1

同余的定義

由同余的定義可以得到以下兩個同余關系成立的充分必要條件:

2.2

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

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

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

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

結論：棄九法只能用來檢驗計算結果是否是錯的，但是并不能保證計算的正確性。

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

2.1

同余的定義

由同余的定義可以得到以下兩個同余關系成立的充分必要條件:

2.2

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

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

《初等數(shù)論》

2.3

剩余類與剩余系

《初等數(shù)論》

2.4

幾個重要的定理

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

證明：

證明：

Euler定理與Fermat定理的應用：

證明：

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

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

2.5

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

2.5.1

一次同余式的解

一次同余式的幾種解法

(假設同余式均有解).

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

Ⅳ.

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

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

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

2.5.2

中國剩余定理與一次同余式組的解法

《初等數(shù)論》

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

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

4.1

一次同余式的解

一次同余式的幾種解法

(假設同余式均有解).

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

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

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

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

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

4.2孫子定理（中國剩余大定理）

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

《初等數(shù)論》

2.6

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

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

注:上述定理也給出了此類同余式的一個解法，用下面的例題來詳細說明此定理

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

《初等數(shù)論》

2.7

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

2.7.1

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