§2.1 数论预备知识简介

闵可夫斯基(H.Minkowski)说：整数是全部数学的基础．每个人最初接触的都是正整数——自然数．为了看清楚数字与数学文化的联系．这里先简要介绍数论(数字的理论)的相关知识．

2.1.1 关于数论

数论是研究整数性质的一门数学分支．数论包括初等数论，解析数论，代数数论，丢番图(Diophantus，公元250年左右)逼近，超越数论等．现代数论已经深入到数学的一切分支．

数学王子高斯说：算术给予我们一个用之不尽的、充满有趣真理的宝库．这些真理不是孤立的，而是以相互最密切的关系并立着，而且随着科学的每一成功的进展，我们不断地发现这些真理间的新的、完全意外的接触点．

事实上，初等数论以算术方法为主要方法．初等数论中某些问题的研究促成新的数学分支的产生．近数十年来，初等数论在计算机科学，组合数学，代数编码，计算方法，信号的数字处理等领域内得到广泛的应用．

数论的特点：表面简单，实际难．所谓表面简单，是因为数论的主要定理的表达都不难理解．但证明起来，却需要极其艰深和复杂的数学工具，比如费尔马猜想、哥德巴赫猜想．许多中学生都想试一试．所以，这里必须指出，研究经典数论问题必须有坚实的数学基础，否则会劳而无功，浪费青春．

2.1.2 数论的基本知识

1.正整数，负整数，零统称为整数．

2.b被a(a≠0)除时，如果余数是0，即存在整数q，使得b=aq，则称a整除b，或者b可以被a整除，记做a|b，此时也称b是a的倍数，a是b的因数．

3.大于1且除了1和它自身外无其他因数的整数称为素数(或质数)，1以外的非素数称为合数．

4.将整数表示为一些素数的乘积称做互素因数分解．

5.整数a₁，a₂，…，a_n的公共倍数称为a₁，a₂，…，a_n的公倍数．最小的正公倍数称为最小公倍数，记为［a₁，a₂，…，a_n］．

6.整数a₁，a₂，…，a_n的公共因数称为a₁，a₂，…，a_n的公因数．最大的公因数称为最大公因数，记为(a₁，a₂，…，a_n)．

7.当(a，b)=1时，称a和b互素．

8.设m为正整数，若整数a和b之差可以被m整除，称a和b关于模m同余．记做a≡b(mod m)．

9.不大于a而与a互素的数的个数叫做Euler函数．

10.(算术基本定理)每个大于1的整数要么是素数，要么是若干素数的乘积，一个数的素因数分解式是惟一的．

这说明分解的方法可以是多种多样的．特别对大合数更是如此．但一个重要的事实是，不管这种素因数分解是如何实现的，除了这些因数的次序外，所得的结果总是一样的，即在同一个数的任意两个素因数分解中，素数是相同的．且每个素数均出现相同的次数．

例

60=4×15=2×2×3×5

60=30×2=15×2×2=3×5×2×2

11.(欧几里得算法)设a，b为两个整数(a≥b)，则存在两数q，r≥0，使得

a=bq+r其中r=0或r＜|b|．