同余理論在中學數學中的應用

侯焱櫪

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

關鍵詞：同余理論;整除;余數;不定方程

一、引言

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

二、同余理論

2.1同余的概念及其基本性質

2.1.1同余的概念

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

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

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

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

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

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

2.1.2同余中的幾個基本重要性質

性質1 若，則

性質2 若，，則（傳遞性）

性質3 若，，則：

（1）;

（2）;

（3）。

推論 若，則。

證 當時，是的倍數，從

可知也是的倍數，所以則。

2.2同余理論中的定理

2.2.1費馬小定理

若是素數，是正整數，那么

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

若，則，故。

推論 若，則。

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

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

），，…，

的正整數解是

其中是同余式的正整數解且。

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

另一方面，因此，，故：

即為的解。

若，是適合式的任意兩個整數，則：

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

2.3歐拉函數與簡化剩余系

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

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

簡化剩余系的特點：有個整數，兩兩不同余，任一數與互質。

推論 在簡化剩余系中若，是兩個互質的正整數，則：。

定理 設，則，其中為一個數的標準分解式。

證明 由推論既得：

今將證

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

所以由，既得：。

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

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

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

定理 一次同余式

，

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

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

定義 幾個一次同余式聯立，稱為一次同余式組。

例：

三、同余理論在中學數學中的應用

3.1用于求解一次同余式

例1 解同余式則。

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

例2 求一次同余方程：。

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

解∵

∴一次同余方程有兩個解

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

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

例3 解同余式

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

的形式來求解。

解∵，

∴同余式有個解

考慮方程：

即：

解得

（令：）

則

=

令，則

∴，則同余式的解為：

∴，，，，，，，，。

3.2用于求解一次同余式組

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

例4設上述題的問物幾何為，則問題轉化為解同余式組：

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

解∵，，

又∵，，

∴，，

∴，即為或。

3.3用于求解質數

例5 求從到中與互質的整數。

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

解 因為=，所以根據定理有：=，所以與互質的數的個數

。

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

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

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

即：;右邊有：，根據棄九法，左邊得：

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

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

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

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

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

3.5平方和問題

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

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

方和的充要條件是沒有形如的質因數。

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

設，，

則

也是兩個數的平方和，則。

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

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

∵，

∴=

則

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

參考文獻：

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

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

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