同余理論在中學(xué)數(shù)學(xué)中的應(yīng)用

侯焱櫪

摘要：本文主要運用同余理論解決在中學(xué)數(shù)學(xué)中的所出現(xiàn)的一些實際問題，由具體的例子出發(fā)做出具體的解題方法，系統(tǒng)的闡述了同余理論的相關(guān)重要性質(zhì)及其應(yīng)用，特別是一些研究的思想方法。同時同余理論在中學(xué)數(shù)學(xué)中是一個新知識點，應(yīng)用同余理論解題可加深學(xué)生對解題的印象，同時也拓展學(xué)生的解題思維與能力，也可以方便學(xué)生的運算。

關(guān)鍵詞：同余理論;整除;余數(shù);不定方程

一、引言

同余理論是初等數(shù)論中旳一個基本的核心理論。同余理論包含了數(shù)論所特有的思想概念及其方法，是在掌握了整除后對整數(shù)的性質(zhì)及應(yīng)用做出進一步的研究，也是整除概念的拓展，同余這個概念最早是由德國的數(shù)學(xué)家高斯（C.F.Gauss1777-1855）所提出，同時在中國的《孫子算經(jīng)》中也曾提出過“物不知其數(shù)”的問題，成為了世界上最早提出解同余式組的國家。

二、同余理論

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

2.1.1同余的概念

定義 給定一個正整數(shù)，把它叫做模，設(shè)，是兩個整數(shù)，如果用正整數(shù)去除和所得的余數(shù)相等，則稱與對于模同余，記作，讀作同余模;若余數(shù)不相同，就稱與關(guān)于模不同余，記作[1]。

例如 3除17余2，3除35也余2，即17與35對于模3是同余的，記作。

此外，同余的概念還可以用以下方式定義：

（1）若，則與對于模同余;

（2）若=+（為任意整數(shù)），則與對于模同余。

定理2.1整數(shù)，對于模同余的充分與必要條件是，即=+（為任意整數(shù)）

2.1.2同余中的幾個基本重要性質(zhì)

性質(zhì)1 若，則

性質(zhì)2 若，，則（傳遞性）

性質(zhì)3 若，，則：

（1）;

（2）;

（3）。

推論 若，則。

證 當時，是的倍數(shù)，從

可知也是的倍數(shù)，所以則。

2.2同余理論中的定理

2.2.1費馬小定理

若是素數(shù)，是正整數(shù)，那么

證明 因為是素數(shù)，在中有個數(shù)與互質(zhì)，所以;若，由歐拉定理得：

若，則，故。

推論 若，則。

2.2.2中國剩余定理（孫子定理）

若，并且是兩兩互素的個正整數(shù)，令，，，那么滿足同余式組

），，…，

的正整數(shù)解是

其中是同余式的正整數(shù)解且。

證明 由，，既得，固由同余式有解的充要條件知對每一，有一存在，使得：

另一方面，因此，，故：

即為的解。

若，是適合式的任意兩個整數(shù)，則：

，，因，于是，故的解只有，證完。

2.3歐拉函數(shù)與簡化剩余系

定義 歐拉函數(shù)是定義在正整數(shù)上的函數(shù)，它在正整數(shù)上的值等于序列中與互質(zhì)的數(shù)的個數(shù)，即表示不大于而與互質(zhì)的正整數(shù)的個數(shù)。

定義 如果一個模的剩余類里面的數(shù)與互質(zhì)，就把它叫做一個與模互質(zhì)的剩余類。在與?；ベ|(zhì)的剩余類中，從每一類各取一個數(shù)所做成的數(shù)的集合，叫做模的一個簡化剩余系[1]。

簡化剩余系的特點：有個整數(shù)，兩兩不同余，任一數(shù)與互質(zhì)。

推論 在簡化剩余系中若，是兩個互質(zhì)的正整數(shù)，則：。

定理 設(shè)，則，其中為一個數(shù)的標準分解式。

證明 由推論既得：

今將證

由的定義知等于從減去中與不互質(zhì)的數(shù)的個數(shù)。由于是質(zhì)數(shù)，故等于從減去中被整除的數(shù)的個數(shù)，由整數(shù)的可除性知中被整除的數(shù)的個數(shù)是，所以，

所以由，既得：。

2.4一次同余式與一次同余式組

定義 如果表示多項式，其中是正整數(shù);再設(shè)是一正整數(shù)，則：叫做模的同余式。

定義 同余式中含有一個未知數(shù)，且未知數(shù)的最高次數(shù)是一次的稱為一元一次同余式。

定理 一次同余式

，

有解的充要條件是且。（其中為解的個數(shù)，且同余式最后的解為：。

證明 設(shè)，若有解，則由定理1.1知適合的解可表示為：，，，此式對模來說可以寫成：，，但，是對模兩兩不同余的，故有個解。

定義 幾個一次同余式聯(lián)立，稱為一次同余式組。

例：

三、同余理論在中學(xué)數(shù)學(xué)中的應(yīng)用

3.1用于求解一次同余式

例1 解同余式則。

解 由于，且，所以該方程無解。

例2 求一次同余方程：。

分析由定理得：，且，所以同余式有且有兩個解，同時可化簡為，從而迅速求得。

解∵

∴一次同余方程有兩個解

則可化簡為：，由同余的性質(zhì)可得，即，解得：，且一次同余方程的另一解為：。

對于簡單的一次同余方程，可根據(jù)同余的性質(zhì)直接求解出來。但對于數(shù)字較大的一次同余方程即可轉(zhuǎn)化為方程：即，且有解的充要條件為，并且解為，，。

例3 解同余式

分析 由于同余式所涉及到的數(shù)字比較大，直接求解難度比較大，本題可把化為方程：

的形式來求解。

解∵，

∴同余式有個解

考慮方程：

即：

解得

（令：）

則

=

令，則

∴，則同余式的解為：

∴，，，，，，，，。

3.2用于求解一次同余式組

對于求解同余式組，我國早在孫子算經(jīng)中就提出了”物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問物幾何？”的問題[1]。

例4設(shè)上述題的問物幾何為，則問題轉(zhuǎn)化為解同余式組：

分析在這里，，，，，，，，=，=。

解∵，，

又∵，，

∴，，

∴，即為或。

3.3用于求解質(zhì)數(shù)

例5 求從到中與互質(zhì)的整數(shù)。

分析與不互質(zhì)的為，，的倍數(shù)，根據(jù)初等的方法同樣可以把與互質(zhì)的數(shù)的個數(shù)求解出來，但求解起來比較麻煩，若把分解為標準分解式得：，則根據(jù)定理很快就能解出答案。

解 因為=，所以根據(jù)定理有：=，所以與互質(zhì)的數(shù)的個數(shù)

。

3.4用棄九法檢查加法和乘法中的錯誤

用一般的算數(shù)方法判斷一個較大算數(shù)中是否有加法和乘法的計算錯誤是很麻煩的事，但采用同余中的棄九法檢查計算中加法和乘法的正確性卻是方便的。例如以下給定的加法：

將各數(shù)的各位數(shù)字相加之后再相加，左邊有：

即：;右邊有：，根據(jù)棄九法，左邊得：

，右邊得：，由于左邊和右邊檢驗的數(shù)不相同，即上式的加法計算錯誤。

同樣這一方法也適用于乘法，如：

由棄九法左端有：，右端有：，即上式的乘法計算錯。

以上檢查辦法只當時，方能使用.這種辦法若檢查出被乘數(shù)與乘數(shù)之積與所給數(shù)關(guān)于9同余，此時無法決定乘法是否正確。例如：，，但。

引理3.1，對都成立[2]。

3.5平方和問題

引理3.2若正整數(shù)和均是兩個數(shù)的平方和，則也是兩個數(shù)的平方和，于是任意有限個兩個數(shù)的平方和之積仍是兩個數(shù)的平方和[3]。

定理3.1若，且沒有平方因數(shù)，則能表成兩個整數(shù)的平

方和的充要條件是沒有形如的質(zhì)因數(shù)。

證明 若沒有形如的質(zhì)因數(shù)，則只有的質(zhì)因數(shù)或質(zhì)因數(shù)，由定理知每個+1型的質(zhì)因數(shù)都可寫成兩個數(shù)的平方和，以及，知的質(zhì)因數(shù)都是兩個數(shù)的平方和。

設(shè)，，

則

也是兩個數(shù)的平方和，則。

例8 判斷與是否為二平方和，若為平方和，則是那兩個數(shù)的平方和？

解 ①由定理知可分解為，則無平方因子部分為，由于，，即，則由定理可知沒有形如的質(zhì)因數(shù)，所以為二平方和。

∵，

∴=

則

②因為素數(shù)且，所以由定理知不是二平方和。

參考文獻：

[1]閔嗣鶴，嚴士健.初等數(shù)論[M].北京：高等教育出版社，2003（12）：48-76

[2]李永新，公務(wù)員考試專用教材[M].人民日報出版社，2015：5

[3][美]杜德利著，周仲良譯[M].哈爾濱工業(yè)大學(xué)出版社，2011（3）：28-389-123