《数学竞赛辅导》——初等数论.pdf

特别说明特别说明 此资料来自百度文库 您目前所看到的文档是使用的抱米花百度文库下载器抱米花百度文库下载器所生成 此文档原地址来自 感谢您的支持 抱米花 h t t p w e n k u b a i d u c o m v i e w b d 3e 0468561252d 380e b 6e d c h t m l 学学学学 初等初等初等初等部分部分部分部分 上中学上中学上中学上中学道生道生道生道生 是学中最重要的一部分 特是在 1991 年 IMO 在中国行 国际上那一年年 因 6 道 IMO 中有 5 道与有 的魅力在于它可以适合小孩到老头 只要有算基的人均可以研究在前几年盛广东的一位农民学好者明了哥德巴赫猜想 然 一言最被澄清了 可是也明了最的 适合于任何人去研究 初等最基的理在于整除 由它可以演化出多定理 做 其实只要整除理即可 然而要很快地解决 要我多见 以及学大量的解技巧 里我介一下中必需的一个容 于 Nr q Nb a 足 r b q a 其中 b r b 知 91 b 由 11962 2 b 知 451963 b 故 4519 b 又因 109321962 2 有12个正 分1 2 3 6 9 18 109 218 327 654 981 1962 所以 181 b 从而 19 b 又由 111991951987 2 知 11 9 5 z y x 例例例例6666 设 n 是五位 第一个不是零 m 是由 n 取消它的中间一个后所成的四位 确定一切 n 使得 m n 是整 第3届加拿大学 解 设 v u z y x x y z u v n 10101010 234 其中 9 2 1 0 L v u z y x 且 1 x v u y x x y u v m 101010 23 而 m n k 是整 可 n m 9 即 101010 9 23 v u y x v u z y x 10101010 234 即 z y x v u 223 101010880 然是成立的 又可 m n 11 即 v u z y x 10101010 234 101010 11 23 v u y x 即 v u y x z 1010101010 2232 然也是正确的 于是 m n m 119 即 119 故 3 b a 若 9 b a 然可以 此共有2 8 10个 若 b a 9 6 b a 或 12 b a 样的共有24 42 48 84共4个 上所述 共有9 1 9 10 4 33个 例例例例8888 如果一个正整 n 在三制下表示的各字之和可以被3整除 那么我 n 好的 前2005个 好的 正整之和是多少 2005年中国奥林匹克作体夏令 解 首先考 好的 非整 考察如下两个引理 引理1 在3个非整 23 13 3 n n n n 是非整 中 有且有1个是 好的 明 在三个非整的三制表示中 0 1 2各在最后一位出一次 其作各位字相同 于是三个各位字之和是三个的正整 其中有且有一个能被3整除 即 好的 引理1得 引理2 在9个非整 89 19 9 n n n L n 是非整 中 有且有3个是 好的 把3个 好的 非整化成三制 0 1 2恰好在三个三制的最后一位各出一次 明 由引理1不得知在9个非整 89 19 9 n n n L n 是非整 中 有且有3个是 好的 另一方面 在三个 好的 非整的三制表示中 最高位与倒第三位完全相同 倒第二位分取0 1 2 若它使它成 好的 非整 最后一位不相同 引理2得 所有 好的 非整按从小到大的序排成一列 设第2004个 好的 非整 m 根据引理1 得 3200432003 m 即 60126009 b 存在整 q 和 r 使得 r b q a 其中 b r 0 并且 q 和 r 由上述条件唯一确定 整 q 被 a 被 b 除得的 不完全 商 r a 被 b 除得的余 注意 r 共有 b 种可能的取值 0 1 1 b 若 0 r 即 a 被 b 整除的情形 易知 余除法中的商实际上 b a 不超 b a 的最大整 而余除法的核心是于余 r 的不等式 b r 0 明 a b 的基本手法是 a 分解 b 与一个整之 在初的中 种的分解常通在一些代式的分解中取特殊值而生 下面两个分解式在类中用很多 见例 1 例 2 若 n 是正整 1221 n n n n n n y x y y x x y x y x L 若 n 是正奇 1221 n n n n n n y x y y x x y x y x L 在上式中用 y 代 y 7 如果在等式 m k k n i i b a 11 中取去某一外 其余各均 c 的倍 一也是 c 的倍 8 n 个整中 有且只有一个是 n 的倍 9 任何 n 个的整之一定是 n 的倍 特地 三个的正整之能被 6 整除 2 奇奇奇奇 偶有如下性偶有如下性偶有如下性偶有如下性 1 奇 奇 偶 偶 偶 偶 奇 偶 奇 偶 偶 偶 奇 偶 偶 奇 奇 奇 即任意多个偶的和 差 仍偶 奇个奇的和 差仍奇 偶个奇的和 差偶 奇与偶的和奇 和偶 2 奇的平方都可以表示成 18 m 的形式 偶的平方可以表示 m 8 或 48 m 的形式 3 任何一个正整 n 都可以成 l n m 2 的形式 其中 m 整 l 奇 4 若有限个整之奇 其中每个整都是奇 若有限个整之偶 些整中至少有一个是偶 两个整的和与差具有相同的奇偶性 偶的平方根若是整 它必偶 3 完全平方及其性完全平方及其性完全平方及其性完全平方及其性 能表示某整的平方的完全平方 平方 平方有以下性与 1 平方的个位字只可能是 0 1 4 5 6 9 2 偶的平方是 4 的倍 奇的平方被 8 除余 1 即任何平方被 4 除的余只有可能是 0 或 1 3 奇平方的十位字是偶 4 十位字是奇的平方的个位一定是 6 5 不能被 3 整除的的平方被 3 除余 1 能被 3 整的的平方能被 3 整除 因而 平方被 9 也合乎的余 0 1 4 7 且此平方的各位字的和被 9 除的余也只能是 0 1 4 7 6 平方的的个奇 7 任何四个整的乘加 1 必定是一个平方 8 设正整 b a 之是一个正整的 k 次方幂 2 k 若 b a 1 b a 都是整的 k 次方幂 一般地 设正整 c b a L 之是一个正整的 k 次方幂 2k 若 c b a L 两两互素 c b a L 都是正整的 k 次方幂 4 整的尾整的尾整的尾整的尾及其性及其性及其性及其性 整 a 的个位也整 a 的尾 并 a G a G 也尾函 尾函具有以下性 1 a GG a G 2 21 n a a a G L 21 n a Ga Ga GG L 3 21 n a a a G L 21 n a Ga Ga GG L 4 0 10 a G 10 b Gb a G 5 若 c b a 10 b Ga G 6 Nk a a Ga G k 44 7 a Za a 的除 1 以外的最小正因 q 是一个 素 如果 aq a q 2 若 p 是 素 a 任一整 必有 a p 或 pa 1 3 设 n a a a 21 L n 个整 p 素 且 n a a a p L 21 p 必整除某个 i a n i 1 4 算基本定理 任何一个大于 1 的正整 a 能唯一地表示成 素 因的乘 不因的排列序 5 任何大于 1 的整 a 能唯一地成 k i p p p a k a k a a 2 1 21 21 LL 的形式 其中 i p 素 j i p p j i n 例例例例 4 设 nm 是正整 2 m 明 12 m 12 n 明 首先 mn 易知成立 事实上 nm 平凡 mn m 最后 mn 的情形可化上述特殊情形 由余除法 m r r m p n q 由于 122 12 12 r r m q n 从而由若 n 是正整 1221 n n n n n n y x y y x x y x y x L 知 12 12 m q m 而 m r 也有 12 m 12 n 就明了本的 例例例例 5 设正整 d c b a 足 c d a b 明 d c b a 不是 素 法一 由 c d a b 可设 n m b d c a 其中 1 n m 由 n m c a 意味着有理 c a 的分子 分母去了某个正整 u 后得既分 n m 因此 n ucm ua 同理 存在正整 v 使得 m v d n v b 因此 d c b a v u n m 是两个大于 1 的整之 从而不是素 注 若正整 d c b a 适合 c d a b d c b a 可分解 及 的形式 一果在某些的解决中很有作用 法二 由 c d a b 得 a c d b 因此 a d a c a d c a c d a d c b a 因 d c b a 是整 故 a d a c a 也是整 若它是一个素 设 p 由 a p d a c a 可见 p 整除 d a c a 从而素 p 整除 ca 或 d a 不妨设 p ca pca 合 推出 a d a 而是不可能的 因 1 d 例例例例 6 求出有序整 nm 的个 其中 991 m 991 n n m n m 3 2 是完全平方 1999 年美国学邀 解 由于 991 m 991 n 可得 n m n m 3 2 4 4 2 n m n m 2 2 n m 又 2 n m n m n m 3 2 于是 2 n m n m n m 3 22 2 d d 有素因子 p 从而由 知 2 b p 因 p 是素 故 b p 合 b a p 知 a p 从而由 p 122 b a 得 p 1 是不可能的 故 1 d 从而由 推知正整 b a 与 122 b a 都是完全平方 例例例例 8 明不存在正整 n 使 2n 2 1 3n 2 1 6n 2 1 都是完全平方 明 假设存在样的正整 n 使 2n 2 1 3n 2 1 6n 2 1 都是完全平方 那么 2n 2 1 3n 2 1 6n 2 1 也必定是完全平方 而 2n 2 1 3n 2 1 6n 2 1 36 n 6 36 n 4 11 n 2 1 23 36 n n 36 n 6 36 n 4 9 n 2 23 136 n n 36 n 6 36 n 4 12 n 3 9 n 2 6 n 1 所以 n m 明 12 12 22 m n 解 由 12 2 m 12 2 12 1111 2222 n n m n n L 故 12 1 2 n 12 2 m 又因 12 1 2 n 12 2 n 12 2 n 从而 12 2 n 12 1 2 n 于是由整除的性知 12 12 22 m n 3 明 于任意正整 n 200520052005 21 n L 不能被 2 n 整除 明 只需 2 2 n 2 200520052005 21 n L 即可 因若 n 是正整 1221 n n n n n n y x y y x x y x y x L 若 n 是正奇 1221 n n n n n n y x y y x x y x y x L 故 2 n 20052005 2 n 2 n 20052005 1 3 n 2 n 20052005 2 n 所以 2 n 2 20052005 2 n L 又因 232 n 所以 2 n 2 所以 2 n 2 20052005 2 n L 2 即 2 n 2 200520052005 21 n L 命得 4 已知 n 正奇 求 1236 60 n n n 明 因若 n 是正整 1221 n n n n n n y x y y x x y x y x L 若 n 是正奇 1221 n n n n n n y x y y x x y x y x L 所以 n n 36 3 12 3 n 从而 1236 3 n n n n n 26 4 13 4 n 从而 1236 4 n n n 16 5 n n n 23 5 从而 1236 5 n n n 又 1 5 4 3 且60543 所以 1236 60 n n n 5 设a b c 足不等式1 a b c 的整 且 a b 1 b c 1 c a 1 能被a b c 整除 求所有可能 a b c 1989年上海 解 a b 1 b c 1 c a 1 a 2 b 2 c 2 a b c a b c a b a c b c 1 a b c a b 1 b c 1 c a 1 存在正整k 使a b a c b c 1 k a b c k k 1 若a 3 此1 矛盾 已知a 1 只有a 2 a 2 代入 中得2b 2c 1 b c 即 1 0 b 4 知b 3 从而易得c 5 明 在此例中通因k 的范 从而逐步确定a b c 是一重要解技巧 第三第三第三第三 整的性及其用整的性及其用整的性及其用整的性及其用 2 基知基知基知基知 最大公与最小公倍是中的一个重要的概念 里我主要两个整互素 最大公 最小公倍等基本概念与性 定义定义定义定义 1 最大公 设 b a 不全零 同整除 b a 的整 如 1 它的公 因 b a 不全零 故 b a 只有有限多个 我其中最大一个 b a 的最大公 用符号 b a 表示 然 最大公是一个正整 b a 1 即b a 的公只有 1 我 a 与 b 互素 互 是中的非常重要的一个概念 同样 如果于多个 不全零 的整 c b a L 可类似地定义它的最大公 c b a L 若 c b a L 1 c b a L 互素 注意 此不能推出 c b a L 两两互素 但反 若 c b a L 两两互素 然有 c b a L 1 由最大公的定义 我不得出最大公的一些性 例如任意改变 b a 的符号 不改变 b a 的值 即 b a b a b a 可以交 b a a b b a 作 b 的函 以 a 周期 即于任意的实 x 有 a x b a b a 等等 了更地介最大公 我出一些常用的一些性 1 设 b a 是不全 0 的整 存在整 yx 使得 b a b y a x 2 裴蜀定理 两个整 b a 互素的充要条件是存在整 yx 使得 1 b y a x 事实上 条件的必要性是性 1 的一个特例 反 若有 yx 使等式成立 不妨设 d b a b d a d 故 a x d 及 b y d 于是 b y a x d 即 1 d 从而 1 d 3 若 b m a m b a m 即 b a 的任何一个公都是它的最大公的 4 若 0 m b a m m b m a 5 若 d b a 1 d b d a 因此两个不互素的整 可以自然地生一互素的整 6 若 1 1 m b m a 1 m a b 也就是 与一个固定整互素的整集于乘法封 并由此可以推出 若 1 b a 于 0 k 有 1 b a k 而有 0 l 有 1 l k b a 7 设 a c b 若 1 c b a b 8 设正整 b a 之是一个正整的 k 次方幂 2 k 若 b a 1 b a 都是整的 k 次方幂 一般地 设正整 c b a L 之是一个正整的 k 次方幂 2 k 若 c b a L 两两互素 c b a L 都是正整的 k 次方幂 定义定义定义定义 2 设 b a 是两个非零整 一个同 b a 倍的它的公倍 b a 的公倍有无多个 其中最小的一个 b a 的最小公倍 作 b a 于多个非零实 c b a L 可类似地定义它的最小公倍 c b a L 最小公倍主要有以下几条性 1 a 与 b 的任一公倍都是 b a 的倍 于多于两个的情形 类似也成立 2 两个整 b a 的最大公与最小公倍足 a b b a b a 但注意 只限于两个整的情形 于多于两个整的情形 类似不成立 3 若 c b a L 两两互素 c b a L c b a L 4 若 d c d b d a L 且c b a L 两两互素 c b a L d 典例分析典例分析典例分析典例分析 例例例例 1 设 yx 是正整 yx 且667 y x 它的最小公倍是最大公的 120 倍 求 yx 解 设 d y x n d y m d x 其中 1 n m 且 nm 于是 m n d y x 所以 120667d m n d n d m d 即 5322923 3 m n d n m 2 1 由 nm n m 22 n m m n nm 明 设 d n m d m m 1 d n n 1 其中 1 11 n m 于是 已知条件化 212111 n m n m 故更有 21211 n m m 从而化 211 n m 但是 1 11 n m 故 1 211 n m 合 211 n m 知必有 1 1 m 同 1 1 n 因此 nm 例例例例 3 设正整 c b a 的最大公是 1 并且 c b a a b 明 b a 是一个完全平方 明 设 d b a d a a 1 d b b 1 其中 1 11 b a 由于 1 c b a 故 1 c b 在中的等式可以化 1111 c b c a b d a 由此可见 1 a 整除 1 c b 因 1 11 b a 故 c a 1 同样可得 c b 1 再由 1 11 b a 便可以推出 c b a 11 设 k b a c 11 其中 k 是一个正整 一方面 然 k 整除 c 另一方面 合 式 得 d 11 b a k 故 d k 从而 d c k 但 1 d c 故 1 k 因此 11 b a d 故 211 d b a d b a 样就明了 b a 是一个完全平方 例例例例 4 b a 都是正整 是否存在整 qp 使得任意的正整 n n ap 与 n b q 互 解 令 b a L b Ls a Lr 1 s r 于是存在整 yx 使得 1 s y r x 令 yqxp 任意的正整 n 设 n b q n a p d n 有 n b q s n a p r d n 即 s b r a n s q r p d n 而 1 s y r x s q r p s b Lr a 所以 11 d n d n 即任意的正整 n n ap n b q 1 例例例例 5 已知 1 20012002 x x x f 明 于任意的正整 m 都有 m f f m f m L m f f f 两两互素 2002 年克地亚 明 设 LL x f f f x p n 其中 f 出 n 次 由 1 1 1 0 f f 故于 Nn 有 1 0 n p x p k 是含有 0 次 1 0 k p 的多式 因此 m p n 除以 1 m 的余 1 设整 1 d 可整除 m p k 和 m p l k 又 m p l k m p p k l m p p k l 除以 m p k 余 1 即 m p l k Q m p k 1 所以 1 d 矛盾 从而可知 m f f m f m L m f f f 两两互素 例例例例 6 求出所有的正整 n m 使得 1 1 3 m n n 是一个整 2006 年山东省第二届夏令 解 由于 1 1 3 m n m 且 1 11 1 333 n m m n n m n 11 1 333 m n m m n 1 1 3 m m n 所以 nm 是的 不妨设 nm nm 2 1 1 1 1 1 1 223 n N n n n n n n n 从而 nm 2 nm 若 1 n 有 2 1 m 所以 2 m 或 3 若 2 n 由于 1 1 3 m n n 是一个整 从而 Nk 使得 1 1 1 3 m n k n n 即 1 k n a b a m m n n b a b a 的充要条件是 m n 2006 年山东省第二届夏令 分析 因 n k n k n n n n k k k b a b b a a b a 所以 k k n n b a b a n k n k n n b a b a 又 n r n r n n n n r r r b a b b a a b a 所以 r r n n b a b a n r n r n n b a b a 令 0 n r r n q m 所以 c b b b c a n 于是 n n b c a 因 1 c b 故可知 1 n n c b 但 1 n b 因而 n n c b 与 a b c n n 是整矛盾 4 设 a b 是不全 0 的整 一切形如 a x b y Ny x 的中 最小的正是 d d a b 5 F n n 2 2 1 F n F m 1 里 nm 第四第四第四第四 同余同余同余同余 同余式性用非常广泛 在处理某些整除性 位制 整分类 解不定方程等方面的中有着不可替代的功能 与之密切相的的定理有拉定理 尔马定理和中国剩余定理 基知基知基知基知 三个函三个函三个函三个函 于任何正整均有定义的函 函 在初等中 所能用到的无非也就有三个 分 高斯 Ga u s s 取整函 x 及其性 除函 d n 和拉 Eu l e r 函 x 和它的算公式 1 高斯 Ga u s s 取整函 x 设 x 是实 不大于 x 的最大整 x 的整部分 x x x x 的小部分 x 例如 0 5 0 7 0 3 0 1415 0 4 3 3 7 50 L 等等 由 x x 的定义可得如下性 性1 1 0 x x x x 性2 1 1 x x x x 性3 设 Za x a x a 性4 y x y x y x y x 性5 1 x x x Zx Zx 性6 于任意的正整 n 都有如下的埃米特恒等式成立 1 2 1 n x n n x n x n x x L 了描述性7 我出如下号 若 a b 且 1 b a b 恰好整除 a a b 例如 我有 2000 5 2000 2 34 等等 其实 由整唯一分解定理 任何大于 1 的整 a 能唯一地成 k i p p p a k a k a a 2 1 21 21 LL 的形式 其中 i p 素 j i p p j i 因而 10 都有 0 m p n 因此 上式实际上是有限的和 另外 此式也指出了乘 n 的准分解式中 素因 p 的指 的算方法 2 除函 d n 正整 n 的正因的个除函 d n 里出 d n 的算公式 d n 1 1 121 k L 121 k L 素唯一分解定理中的指 了叙述地更加明确 我出素唯一分解定理 算基本定理算基本定理算基本定理算基本定理 素唯一分解定理素唯一分解定理素唯一分解定理素唯一分解定理 任何一大于1的整均可以分解素的乘 若不考素乘的先后序 分解式是唯一的 例如 322224 一个整分解成素的乘 其中有些素可以重复出 例如在上面的分解式中 2出了三次 把分解式中相同的素的成幂的形式 我就可以把大于1的正整 a 成 k i p p p a k a k a a 2 1 21 21 LL 1 此式 a 的准分解式 样 算基本定理也可以描述大于1的整的准分解式是唯一的 不考乘的先后序 推推推推1111 若 a 的准分解式是 1 式 d 是 a 的正因的充要条件是 k i a p p p d i i k k 2 1 0 21 21 LL m 若 b a m a 和 b 模 m 同余 作 m o dm b a 若不然 a 和 b 模 m 不同余 作 a m o dm b 例如 15 m o d 434 7 m o d 11000 等等 m b k m o dm c b c a k k 但是同余式的消去律一般并不成立 即从 m o dm b c a c 未必能推出 m o dm b a 可是我却有以下果 6 若 m o dm b c a c m o d c m m b a 由此可以推出 若 1 m c 有 m o dm b a 即在 c 与 m 互素 可以在原同余式两边去 c 而不改变模 一点再一次明了互素的重要性 在提及几个与模相的而有用的性 7 若 m o dm b a d m m o dd b a 8 若 m o dm b a 0 d m o dd m d b d a 9 若 2 1 m o dk i m b a i L m o d 21 n m m m b a L 特地 若 n m m m 21 L 两两互素 有 m o d 21 n m m m b a L 性3 若 k i m b a i i 2 1 m o d L m o d 11 m b a k i k i i i k i k i i i b a 11 性4 设 x f 是系全整的多式 若 m o dm b a m o d m b f a f 一性在算特有用 在算大字的式子 可以改变成与它同余的小的字 使算大大地化 如例3 定义定义定义定义2222 设 1 m a 0 d 是使 m o d 1 m a d 成立的最小正整 0 d a 模 m 的 在取定某 m 后 按照同余系把彼此同余的整一类 些模 m 的剩余类 一个类的任何一个 都类所有的剩余 然 同类的余相同 不同类的余不相同 样我就把全体整按照模 m 划分了 m 个剩余类 10 m r Zq r q m K r 余 在上述的 m 个剩余类中 每一类任意取一个剩余 可以得到 m 个 110 m a a a L 模 m 的一个完全剩余系 例如系模7 下面的每一都是一个完全剩余系 0 1 2 3 4 5 6 7 8 16 3 10 40 20 3 2 1 0 1 2 3 然 一整成模 m 的完全剩余系只需要足两个条件 1 有 m 个 2 各于模 m 两两不同余 最常用的完全剩余系是最小非完全剩余系及值最小完全剩余系 模 m 的最小非完全剩余系是 0 1 2 1 m 即除 m 余可能取到的的全部值 m 奇 值最小的完全剩余系是 2 1 1 0 1 2 1 m m LL m 偶 值最小的完全剩余系有两个 2 1 0 1 1 2 m m LL 1 2 1 0 1 2 m m LL 以上只是我个人同余及剩余类的理解 了方便大家研究 我把有材料上的具体概念出 希望大家好好地研究 定义定义定义定义3333 同余类同余类同余类同余类 设 1 1 0 m o d m r m r x Zx x M r L 每一个样的类模 m 的同余类 明明明明 整集合可以按模 m 分类 确切地 若 a 和 b 模 m 同余 a 和 b 属同一类 否不属于同一类 每一个样的类模 m 的一个同余类 由余除法 任一整必恰与0 1 1 m 中的一个模 m 同余 而0 1 1 m m 个彼此模 m 不同余 因此模 m 共有 m 个不同的同余类 即 1 1 0 m o d m r m r x Zx x M r L 例如 模2的同余类共有两个 即通常的偶类与奇类 两类中的分具有形式 k 2 和 12 k k 任意整 定义定义定义定义4444 剩余类 设 m 是正整 把全体整按模 m 的余分成 m 类 相的 m 个集合 110 m KKK L 其中 10 m r Zq r q m K r 余 模 m 的一个剩余类 以下是几条常用性以下是几条常用性以下是几条常用性以下是几条常用性 1 U 10 m i i KZ 且 j i KK j i I 2 每一个整在 110 m KKK L 的一个里 3 于任意 Zb a r Kb a 的充要条件是 m o dm b a 定义定义定义定义5 完全剩余系 一 s y y y 21 L 模 m 的完全剩余系 如果任意 a 有且有一个 j y 是 a 模 m 的剩余 即 m o d m y a j 一种法更好理解 设 110 m KKK L 模 m 的全部剩余类 从每个 r K 中任取一个 r a 得 m 个 110 m a a a L 成的 叫做模 m 的一个完全剩余系 明明明明 在 m 个剩余类中各任取一个作代表 样的 m 个模 m 的一个完全剩余系 模 m 的完系 句 m 个 m c c c 21 L 模 m 的一个完系 是指它彼此模 m 不同余 例如0 1 2 1 m 是模 m 的一个完系 作是模 m 的最小非完系 性性性性 1 m 个整构成模 m 的一个完全剩余系两两模不同余 2 若 1 m a x 与 b a x 同跑遍模 m 的完全剩余系 典例分析典例分析典例分析典例分析 例例例例1111 解方程 5715865 x x 解 因左边是整 因而右边的分式也是整 所以 086557155715865 x x x x 于是 0409081 x 从而 1 40 90810 x 故 4090810 x 但是 5 715 x 是整 故 7515 t x Zt 代入前面的不等式 得 Zt t 4030390 直接察即知 1 0 t 于是 5 4 15 7 x 例例例例2222 100 的十位制表示中 未尾地有多少位全是零 解 命等价于100 最多可以被10的多少次方整除 因 5210 因而100 中2的指大于5的指 所以100 中5的指就是所需求出的零的位 由 2442051005100 2 即可知100 的未尾地有24位全是零 例例例例3333 求 2633 46257 被50除所得的余 解 由于 2633 46 x 是于 x 的整系多式 而 50 m o d 7257 于是知 2633 46257 50 m o d 467 2633 又注意到 50 m o d 1497 2 故 2633 46257 50 m o d 467 2633 26162 467 7 50 m o d 353 467 467 1 2626262616 又 50 m o d 772502433 5 所以 2633 46257 3 7 3 3 555 50 m o d 292137 7 22 注意到 50290 因而29就是所求的余 明 在上述程中 我已经看到 50 m o d 1497 2 的作用 一般而言 知道一个整的多少次幂于模同余于 1 是非常有用的 事实上 若 m o d 1 m a k 大的指 n 利用余除法定理 可得 k r r k q n Q 7 11 b n n a a a 由 式及 5 1 10 a a 可知 任意 n a Nn 正整 2 两边配方 得 3 1 1 9 211121 n n n n n n n n a a a a a a a a 由 式 11 9 n n n n n a a a a a 1 m o d 3 n n a a 1 n n a a 10 1 n a a 0 m o d 3 1 3 n n a a 正整 式成立 1 1 n n a a 是完全平方 例例例例 8 若 12 13 n n n 可以成有限小 那么自然 n 的值是多少 解解解解 由于 1 13 n n 若 13 n 与 12 n 互素 分 12 13 n n n p 是既分 若 13 n 与 12 n 不互素 设它的公 d 且 1 d 设 d b n d a n 12 13 5 12 3 13 2 32 n n b a d 故 13 n 与 12 n 的公是 5 此分 p 的分子 分母只有公 5 由于 p 可以成有限小 故分之后 p 的分母除了 2 5 以外 有其它的公 因此 m k n n 52 12 因 12 n 是奇 1 12 n n 故 m k n n 5122 即152 1 m k 由于 15 m 4 m o d 2 故 4 m o d 22 1 k 从而 0 k 即 1 0 n m 故只有 p n 1 才是有限小 1 求方程 5715865 x x 的实解 x 答案 5 4 15 7 x 2 若 16 n 出至少5个 n 的值 答案 17 32 34 40 48 3 求 5010 19991998 被25除所得的余 答案 24 4 设整 n 使 m o d 1 m a n 些 n 中最小的正整 n 特地 若 1 m a m 明 设 m m 就是1 2 1 m 中与 m 互素的的个 比如 p 是素 有 1 p p 引引引引理理理理 P P11 m P m m 可用容斥定理 明略 定理定理定理定理1111 拉 Eu l e r 定理 设 m a 1 m o d 1 m a m 明 取模 m 的一个既剩余系 21 m s b b b s L 考 s a b a b a b 21 L 由于 a 与 m 互 故 1 s j a b j 仍与 m 互 且有 i a b 1 s j i a b j 于是每个 s j 1 都能找到唯一的一个 s j 1 使得 m o d m b a b j j 种系 是一一的 从而 m o d m o d 11 1 m b m b a b s j j s j j s j j m o d 11 m b b a s j j s j j s 1 1 s j j b m Q m o d 1 m a s 故 m o d 1 m a m 分析与解答 要 m o d 1 m a m 我得设法找出 m 个 n 相乘 由 m 个我 想到 m 2 1 L 中与 m 互的 m 的个 21 m a a a L 由于 m a 1 从而 21 m a a a a a a L 也是与 m 互的 m 个 且两两余不一样 故 21 m a a a L 21 m a a a a a a L m a 21 m a a a L m m o d 而 21 m a a a L m 1 故 m o d 1 m a m 是明中常用的一种方法 使用一剩余系 然后乘一个成另外一剩余系解决 定理定理定理定理2222 尔马尔马尔马尔马 Fe r m a t Fe r m a t Fe r m a t Fe r m a t 小定理小定理小定理小定理 于 p 及任意整 a 有 m o d p a a p 设 p 若 a 是 p 的倍 m o d 0 p a a p 若 a 不是 p 的倍 1 p a 由引理及拉定理得 m o d 1 1 p a p p p m o d m o d 1 1 p a a p a p p 由此即得 定理定理定理定理 2 推推推推 设 p a 是与 p 互的任一整 m o d 1 1 p a p 定理定理定理定理3333 威尔威尔威尔威尔 Wi l s o n Wi l s o n Wi l s o n Wi l s o n 定理定理定理定理 设 p m o d 1 1 p p 分析与解答 受拉定理的影响 我也找 1 p 个 然后乘法 明 于 1 p x 在 x p x x 1 2 L 中 必然有一个除以 p 余1 是因 x p x x 1 2 L 好是 p 的一个剩余系去0 从而 1 2 1 1 2 1 p y p x LL 使得 m o d 1 p x y 若 m o d 21 p x y x y 1 p x m o d 0 21 p y y x 21 y y p 故于 1 2 1 21 p y y L 有 1 x y m o d 2 p x y 即于不同的 x 于不同的 y 即 1 2 1 p L 中可两两配 其除以 p 余1 然后有 x 使 m o d 1 2 p x 即与它自己配 m o d 01 2 p x m o d 0 1 1 p x x 1 x 或 m o d 1 p x 1 p x 或 1 x 除 1 1 p x 外 的可两两配 除以 p 余1 故 m o d 11 1 1 p p p 定义 设 x f j 整系多式 k j 1 我把含有 x 的一同余式 m o d 0 j j m x f k j 1 同余方程 特地 x f i 均 x 的一次整系 多式 同余方程一次同余方程 若整 c 同足 m o d 0 j j m c f k j 1 剩余类 m o d m c x Zx x M c 其中 21k m m m m L 同余方程的一个解 作 m o d m c x 定理定理定理定理4444 中国剩余定理中国剩余定理中国剩余定理中国剩余定理 设 k m m m 21 L 是两两互素的正整 那么于任意整 k a a a 21 L 一次同余方程 m o d j j m a x k j 1 必有解 且解可以 m o d 222111 m a NMa NMa NMx k k k L 里 k m m m m L 21 1 k i m m M i i 以及 j N 足 m o d 1 j j j m NM k j 1 即 j N j M 模 j m 的逆 中国定理的作用在于它能言所的同余式模两两互素一定有解 而于解的形式并不重要 定理定理定理定理5555 拉格郎日定理拉格郎日定理拉格郎日定理拉格郎日定理 设 p 是 n 是非整 多式 01 a x a x a x f n n L 是一个模 p n 次的整系多式 即 p n a 同余方程 m o d 0 p x f 至多有 n 个解 在模 p 有意义的情况下 定理定理定理定理6666 若 l a 模 m 的 s 某一正整 足 m o d 1 m a s s 必 l 的倍 以上介的只是一些系统的知 方法 经常在解决中起着突破点的作用 另外有一些小的技巧是在解决 思考中起着排除情况 助分析等作用 有也会起到意想不到的作用 如 偶奇 n n n 4 m o d 0 8 m o d 1 2 不整除整除 n n n 33 3 m o d 0 9 m o d 0 2 里我只介几个直接的用些定理的例子 典例分析典例分析典例分析典例分析 例例例例1 1 1 1 设 1 91 a b 求 91 1212 b a 明 因 13791 故由 1 91 a b 知 1 91 a 从而 1 13 1 7 a a 但是 12 13 6 7 故由拉定理得 7 m o d 11 22612 a a 13 m o d 1 12 a 从而 91 m o d 1 12 a 同理 91 m o d 1 12 b 于是 91 m o d 011 1212 b a 即 91 1212 b a 注明 考整 a 的幂n a 所成的列 LL 2 n a a a 若有正整 k 使 m o d 1 m a k 有 m o d m a a r n 其中 k r r k q n n 且 1 n k 是偶 明 存在整 yx 使得 1 n y n x 且 m o dn k y x 明 我先明 n 素幂 p 成立 实际上 能够明 存在 yx 使 px y 且k y x 若 2 p 条件表明 k 偶 此可取 1 1 k y x 若 2 p 1 1 k y x 与 2 2 k y x 中有一足要求 一般情形下 设 r i p p p n r a r a a 2 1 21 21 LL 是 n 的一个准分解 上面已经明 每个 i p 存在整 i i y x 使得 i p i i y x 且 k y x i i 2 1 r i L 而由中国剩余定理 同余式 2 1 m o d r i p x x i i i L 有解 x 同余式 2 1 m o d r i p y y i i i L 有解 y 不解 yx 符合中的要求 因 i p i i y x 故 i px y 2 1 r i L 于是 1 n x y 又由 知 2 1 m o d r i p y x y x i i i i L 故 m o dn k y x 注 此的表了中国剩余定理最基本的作用 一个于任意正整 n 的 化 n 素幂的 而后者往往是比好处理的 1 设 p 是定的素 明 列 1 2 n n n 中有无多被 p 整除 2 求 x f x x x x 30 1 3 1 2 1 5 1 345 整值多式 3 列 1 31 331 3331 中有无多个合 4 设 n 任意定的正整 明 存在 n 个正整 其中每一个都不是素的幂 5 设 nm 正整 具有性 等式 111 111 n k m k 所有的正整 k 成立 明 n m r 11 其中 r 是某个整 第六第六第六第六 不定方程不定方程不定方程不定方程 所不定方程 是指未知的个多于方程个 且未知受到某些 如要求是有理 整或正整等等 的方程或方程 不定方程也番方程 是的重要分支学科 也是史上最活跃的学域之一 不定方程的容十分丰富 与代 几何 集合等等都有密切的联系 不定方程的重要性在学中也得到了充分的体 每年世界各地的学吉 不定方程都占有一席之地 另外它也是培学生思能力的好材料 学中的不定方程 不要求学生初等的一般理 方法有一定的了解 而且更需要究思想 方法与技巧 造性的解决 在本我看一看不定方程的基性的目 基知基知基知基知 1 不定方程的常见类型 1 求不定方程的解 2 判定不定方程是否有解 3 判定不定方程的解的个 有限个是无限个 2 解不定方程常用的解法 1 代恒等变形 如因式分解 配方 元等 2 不等式估算法 利用不等式等方法 确定出方程中某些变量的范 而求解 3 同余法 等式两边取特殊的模 如奇偶分析 小变量的范或性 得出不定方程的整解或判定其无解 4 构造法 构造出符合要求的特解 或构造一个求解的递推式 明方程有无多解 5 无递推法 以下出几个于特殊方程的求解定理 一一一一 二元二元二元二元一次不定方一次不定方一次不定方一次不定方程程程程 定义定义定义定义1111 形如 c b y a x Zc b ab a 不同零 的方程二元一次不定方程 定理定理定理定理1111 方程 c b y a x 有解的充要是 c b a 定理定理定理定理2222 若 1 b a 且 00 y x c b y a x 的一个解 方程的一切解都可以表示成 t b a a y y t b a b x x 00 t 任意整 定理定理定理定理3333 n 元一次不定方程 c x a x a x a n n L 2211 Nc a a a n 21 L 有解的充要条件是 c a a a n 21 L 方法与技巧 1 解二元一次不定方程通常先判定方程有无解 若有解 可先求 c b y a x 一个特解 从而出通解 不定方程系不大 有可以通察法求得其解 即引入变量 逐减小系 直到容易得其特解止 2 解 n 元一次不定方程 c x a x a x a n n L 2211 可先次求出 332221 d a d d a a n n n d a d 1 若 n d c 方程无解 若 n d c 方程有解 作方程 c x a t d t d x a t d t d x a t d t d x a x a n n n n n n n n n n 11111122333322222211 LLLL 求出最后一个方程的一切解 然后把 1 n t 的每一个值代入倒第二个方程 求出它的一切解 样下去即可得方程的一切解 3 m 个 n 元一次不定方程成的方程 其中 nm 可以消去 1 m 个未知 从而消去了 1 m 个不定方程 方程化一个 1 m n 元的一次不定方程 二二二二 高次不定方程高次不定方程高次不定方程高次不定方程 及其解法及其解法及其解法及其解法 1 因式分解法 方程的一边行因式分解 另一边作因式分解 然后比两边 而求解若干个方程 2 同余法 如果不定方程 0 1 n x x F L 有整解 于任意 Nm 其整解 1 n x x L 足 m o d 0 1 m x x