数论研究整数环中整数最基本性质，整除理论、同余理论和不定方程求解.PDF

数论研究整数环中整数最基本性质 ，整除理论 、同余理论和不定方程求 　　 解构成数论的基本内容 。随着信息技术的飞速发展 ，数论所涉及的知识在信 息领域特别是信息安全领域具有广泛的应用 ，公钥密码标准 ＲＳＡ 算法是基 于大整数分解困难性而设计的 ，通信系统中广泛使用的 ＤｉｆｆｉｅＨｅｌｌｍｅｎ协议 与整数的同余和原根密切相关 。掌握数论的基本知识 ，对于从事信息安全理 论与应用研究具有重要作用 。 ·２ · 信息安全数学基础 １１ 整数的整除 　 全体整数的集合通常用 来表示 ，即 瓕 ｛， ， ， ，…｝ 瓕＝ ０ ± １ ± ２ ± ３ 在整数集合 瓕中，两个整数可以进行加 、减 、乘三种运算 ，并且运算后的结果仍为整数 。 但两个整数进行除法运算后所得 的结果未必为整数 ，比如 除以 所得结果为 ，它是一 ４ ２ ２ ４ 个整数 ，而 除以 所得结果为 ，它不是整数 。 ４ ３ ３ 定义 设 ，是任意两个整数 ， ，如果存在整数 ，使得 ，则称 整 １１ ａｂ ｂ ０ ｃ ａ＝ ｂｃ ｂ 　 ≠ 除 ，记做 ，否则称 不整除 ，记做 。 ａ ｂ ａ ｂ ａ ｂ ａ ｜  如果有 ，称 为 的因数 ， 为 的倍数。显然 是任何整数的因数 ，所有的非 ｂ ａ ｂ ａ ａ ｂ １ ｜ ± 零整数均为 的因数。由整除的定义，易知如下性质成立 ： ０ （）如果 ， ，则 ； １ ｃ ｂ ｂ ａ ｃ ａ ｜ ｜ ｜ （）如果 ， ，则对任意 ， ，均有 （ ）； ２ ｃ ｂ ｃ ａ ｍ ｎ ｃ ｍａ ｎｂ ｜ ｜ 瓕 ｜ ＋ ∈ （）如果 ，且 ，则 ； ３ ｂ ａ ａ ０ ｂ ａ ｜ ≠ ≤ （）如果 ， ，则 ，即 。 ４ ａ ｂ ｂ ａ ａ ｂ ａ ｂ ｜ ｜ ＝ ＝± 例 证明 ：对任意正整数 ，均有 （ ）（ ）。 １１ ｎ ６ ｎｎ １ ２ｎ １