02013初等数论练习题及答案

初等数论练习题一初等数论练习题一 一 填空题 1 2420 27 2420 880 2 设 a n 是大于 1 的整数 若 an 1 是质数 则 a 2 3 模 9 的绝对最小完全剩余系是 4 3 2 1 0 1 2 3 4 4 同余方程 9x 12 0 mod 37 的解是 x 11 mod 37 5 不定方程 18x 23y 100 的通解是 x 900 23t y 700 18t t Z Z 6 分母是正整数 m 的既约真分数的个数为 m 7 18100被 172除的余数是 256 8 1 103 65 9 若 p 是素数 则同余方程 x p 1 1 mod p 的解数为 p 1 二 计算题 1 解同余方程 3x2 11x 20 0 mod 105 解 因 105 3 5 7 同余方程 3x2 11x 20 0 mod 3 的解为x 1 mod 3 同余方程 3x2 11x 38 0 mod 5 的解为x 0 3 mod 5 同余方程 3x2 11x 20 0 mod 7 的解为x 2 6 mod 7 故原同余方程有 4 解 作同余方程组 x b1 mod 3 x b2 mod 5 x b3 mod 7 其中b1 1 b2 0 3 b3 2 6 由孙子定理得原同余方程的解为 x 13 55 58 100 mod 105 2 判断同余方程 x2 42 mod 107 是否有解 1 107 42 1 7 2 7 107 1 107 7 1 3 2 3 107 1 107 3 1 107 2 107 7 107 3 107 2 107 732 107 42 2 1107 2 17 2 1107 2 13 解 故同余方程 x2 42 mod 107 有解 3 求 127156 34 28除以 111 的最小非负余数 2 解 易知 1271 50 mod 111 由 502 58 mod 111 503 58 50 14 mod 111 509 143 80 mod 111 知 5028 509 3 50 803 50 803 50 68 50 70 mod 111 从而 5056 16 mod 111 故 127156 34 28 16 34 28 5028 70 mod 111 三 证明题 1 已知 p 是质数 a p 1 证明 1 当 a 为奇数时 ap 1 p 1 a 0 mod p 2 当 a 为偶数时 ap 1 p 1 a 0 mod p 证明 由欧拉定理知 ap 1 1 mod p 及 p 1 a 1 mod p 立得 1 和 2 成立 2 设 a 为正奇数 n 为正整数 试证 1 mod 2n 2 1 n 2 a 证明证明 设 a 2m 1 当 n 1 时 有 a2 2m 1 2 4m m 1 1 1 mod 23 即原式成立 设原式对于 n k 成立 则有 1 mod 2k 2 1 q2k 2 k a 2 k a2 其中 q Z 所以 1 q2k 2 2 1 q 2k 3 1 mod 2k 3 1 2 k a 其中 q 是某个整数 这说明式 1 当 n k 1 也成立 由归纳法知原式对所有正整数 n 成立 3 设 p 是一个素数 且 1 k p 1 证明 1 k mod p k p 1 C 证明 设 A 得 2 1 C 1 k kppp k p k A p 1 p 2 p k 1 2 k mod p 又 k p 1 故 A 1 k mod p k p 1 C 4 设 p 是不等于 3 和 7 的奇质数 证明 p6 1 mod 84 说明 因为 84 4 3 7 所以 只需证明 p6 1 mod 4 p6 1 mod3 p6 1 mod 7 同时成立即可 证明 因为 84 4 3 7 及 p 是不等于 3 和 7 的奇质数 所以 3 p 4 1 p 3 1 p 7 1 由欧拉定理知 p 4 p2 1 mod 4 从而 p6 1 mod 4 同理可证 p6 1 mod3 p6 1 mod 7 故有 p6 1 mod 84 注 设 p 是不等于 3 和 7 的奇质数 证明 p6 1 mod 168 见赵继源 p86 初等数论练习题二 一 填空题 1 1000 16 除数函数 因数的个数 1000 2340 和函数 所有因数的 和 2 2010 的标准分解式中 质数 11 的次数是 199 3 费尔马 Fermat 数是指 Fn 1 这种数中最小的合数 Fn 中的 n 5 n 2 2 4 同余方程 13x 5 mod 31 的解是 x 29 mod 31 5 分母不大于 m 的既约真分数的个数为 2 3 m 6 设 7 80n 1 则最小的正整数 n 6 7 使 41x 15y C 无非负整数解的最大正整数 C 559 8 1 101 46 9 若 p 是质数 n p 1 则同余方程 x n 1 mod p 的解数为 n 二 计算题 1 试求被 19 除所得的余数 2004 2003 2002 解 由 2002 7 mod 19 20022 11 mod 19 20023 1 mod 19 又由 20032004 22004 22 1002 1 mod 3 可得 20023n 1 20023 n 2002 7 mod 19 2004 2003 2002 2 解同余方程 3x14 4x10 6x 18 0 mod 5 解 由 Fermat 定理 x5 x mod 5 因此 原同余方程等价于 2x2 x 3 0 mod 5 将 x 0 1 2 mod 5 分别代入上式进行验证 可知这个同余方程解是 x 1 mod 5 3 已知 a 5 m 21 求使a x 1 mod m 成立的最小自然数 x 解 因为 5 21 1 所以有欧拉定理知 5 21 1 mod 21 又由于 21 12 所以 x 12 而 12 的所有正因数为 1 2 3 4 6 12 4 于是 x 应为其中使 5 x 1 mod 12 成立的最小数 经计算知 x 6 三 证明题 1 试证 13 54m 46n 2000 提示 可取模 13 进行计算性证明 证明 54m 46n 2000 252m 642n 2000 1 2m 1 2n 2000 2002 0 mod 13 2 证明 Wilson 定理的逆定理 若 n 1 并且 n 1 1 mod n 则 n 是素数 证明 假设 n 是合数 即 n n1n2 1 n1 n 由题设易知 n 1 1 mod n1 得 0 1 mod n1 矛盾 故 n 是素数 3 证明 设ps表示全部由 1 组成的 s 位十进制数 若ps是素数 则 s 也是一个素数 证明 假设 s 是合数 即 s ab 1 a b1 且 n 1 1 0 mod n 则 n 为素数 6 3103被 11 除所得余数是 5 7 1 97 60 三 计算题三 计算题 1 判定 2x3 x2 3x 1 0 mod 5 是否有三个解 x6 2x5 4x2 3 0 mod 5 是否有六个解 解 2x3 x2 3x 1 0 mod 5 等价于 x3 3x2 4x 3 0 mod 5 又 x5 x x3 3x2 4x 3 x2 3x 5 6x2 12x 15 其中 r x 6x2 12x 15 的系数不都 是 5 的倍数 故原方程没有三个解 因为这是对模 5 的同余方程 故原方程不可能有六个解 2 设n是正整数 求 的最大公约数 12 2 3 2 1 2 C C C n nnn 解 设知 d 22n 1 1212 2 3 2 1 2 12 2 3 2 1 2 2CCC C C C nn nnn n nnn d 由 设 2k n 且 2k 1n 即 2k 1 n 则由 2k 1 i 3 5 2n 1 得 d 2k 1 122 11 2 C 2 C2C i n i n k n i n 及 6 1 3 已知 a 18 m 77 求使 ax 1 mod m 成立的最小自然数 x 解 因为 18 77 1 所以有欧拉定理知 18 77 1 mod 77 又由于 77 60 所以 x 60 而 60 的所有正因数为 1 2 3 4 5 6 10 12 15 20 30 60 于是 x 应为其中使 18x 1 mod 77 成立的最小数 经计算知 x 30 四 证明题四 证明题 1 若质数 p 5 且 2p 1 是质数 证明 4p 1 必是合数 证明 因为质数 p 5 所以 3 p 1 可设 p 3k 1 或 p 3k 2 当 p 3k 1 时 2p 1 6k 3 是合数 与题设矛盾 从而 p 3k 2 此时 2p 1 是形如 6k 5 的质数 而 4p 1 12k 9 3 4k 3 是合数 注注 也可设 p 6k r r 0 1 2 3 4 5 再分类讨论 2 设 p q 是两个大于 3 的质数 证明 p2 q2 mod 24 证明 因为 24 3 8 3 8 1 所以只需证明 p2 q2 mod 3 p2 q2 mod 8 同时成立 事实上 由于 p 3 1 q 3 1 所以 p2 1 mod 3 q2 1 mod 3 于是 p2 q2 mod 3 由于 p q 都是奇数 所以 p2 1 mod 8 q2 1 mod 8 于是 p2 q2 mod 8 故 p2 q2 mod 24 3 若 x y R 1 证明 xy x y 2 试讨论 xy 与 x y 的大小关系 注 我们知道 x y x y x y x y 此题把加法换成乘法又如何呢 证明 1 设 x x 0 1 y y 0 1 于是 xy x y x y 所以 xy x y x y x y 2 xy 与 x y 之间等于 大于 小于三种关系都有可能出现 当 x y 时 xy x y 2 1 4 1 7 当 x y 时 xy x y 此时 xy x y 2 3 2 1 4 3 4 1 当 x y 时 xy x y 此时 xy x y 2 1 3 1 6 1 3 1 4 证明 存在一个有理数 其中 d 100 能使 d c d c k 100 73 k 对于 k 1 2 99 均成立 证明 由 73 100 1 以及裴蜀恒等式可知 存在整数 c d 使得 73d 100c 1 从而 由 k 0 是偶数 a1 a2 am 与 b1 b2 bm 都是模 m 的完全剩余系 证明 a1 b1 a2 b2 am bm 不是模 m 的完全剩余系 证明 因为 1 2 m 与 a1 a2 am 都是模 m 的完全剩余系 所以 mod m 1 m i m i i mmm ia 11 22 1 同理 mod m 2 m i i m b 1 2 如果 a1 b1 a2 b2 am bm 是模 m 的完全剩余系 那么也有 10 mod m m i ii m ba 1 2 联合上式与式 1 和式 2 得到 0 mod m 222 mmm 这是不可能的 所以 a1 b1 a2 b2 am bm 不能是模 m 的完全剩余系 4 证明 1 2730 x13 x 2 24 x x 2 25x2 1 3 504 x9 x3 4 设质数 p 3 证明 6p xp x 证明 1 因为 2730 2 3 5 7 13 2 3 5 7 13 两两互质 所以 由 x13 x x x12 1 0 mod 2 知 2 x13 x 13 x13 x 由 x13 x x x12 1 x x2 1 x2 1 x8 x4 1 0 mod 3 知 3 x13 x 由 x13 x x x12 1 x x4 1 x8 x4 1 0 mod 5 知 5 x13 x 由 x13 x x x12 1 x x6 1 x6 1 0 mod 7 知 7 x13 x 故有 2730 x13 x 同理可证 2 3 4 初等数论练习题五初等数论练习题五 一 单项选择题一 单项选择题 1 设 x y 分别通过模 m n 的完全剩余系 若 C 通过模 mn 的完全剩余系 A m n 都是质数 则 my nx B m n 则 my nx C m n 1 则 my nx D m n 1 则 mx ny 2 1 3 5 2003 2005 2007 2009 2011 标准分解式中 11 的幂指数是 A A 100 B 101 C 99 D 102 3 n 为正整数 若 2n 1 为质数 则 n 是 A A 质数 B 合数 C 3 D 2k k 为正整数 4 从 100 到 500 的自然数中 能被 11 整除的数的个数是 B A 33 B 34 C 35 D 36 5 模 100 的最小非负简化剩余系中元素的个数是 C A 100 B 10 C 40 D 4 二 填空题二 填空题 11 1 同余方程 ax b 0 modm 有解的充分必要条件是 a m b 2 高斯称反转定律是数论的酵母 反转定律是指设 p 与 q 是不相同的两个奇质数 2 1 2 1 1 q p p q qp 3 20122012被 3 除所得的余数为 1 4 设 n 是大于 2 的整数 则 1 n 1 5 单位圆上的有理点的坐标是 其中 a 与 b 是不全为 2222 22 22 22 22 2 2 ba ab ba ba ba ba ba ab 或 零的整数 6 若 3258 a 恰好是一个正整数的平方 则 a 的最小值为 362 7 已知 2011 是一素数 则 1 2011 72 三 计算题三 计算题 1 求 32008 72009 132010的个位数字 解 32008 72009 132010 32008 3 2009 32010 32008 2009 2010 36027 3 32 3013 3 mod 10 2 求满足 mn m n 的互质互质的正整数 m 和 n 的值 解 由 m n 1 知 mn m n 于是有 m n m n 设 m a n b 即有 a b ab 显然 a b 且 b a 因此 a b 于是由 2a a2 得 a 2 即 m n 2 故 m 3 n 4 或 m 4 n 3 3 甲物每斤 5 元 乙物每斤 3 元 丙物每三斤 1 元 现在用 100 元买这三样东西共 100 斤 问各买几斤 解 设买甲物 x 斤 乙物 y 斤 丙物 z 斤 则 5x 3y z 100 3 1 x y z 100 消去 z 得到 7x 4y 100 1 显然 x 0 y 25 是方程 1 的解 因此 方程 1 的一般解是 t Z ty tx 725 4 因为 x 0 y 0 所以 0 t 3 12 即 t 可以取值 t1 1 t2 2 t3 3 相应的 x y z 的值是 x y z 4 18 78 8 11 81 12 4 84 四 证明题四 证明题 1 已知 2011 是质数 则有 2011 个2010 999 证明 102011 1 0 mod 2011 个2010 999 2 设 p 是 4n 1 型的质数 证明若 a 是 p 的平方剩余 则 p a 也是 p 的平方剩余 证明 因为质数 p 4n 1 a 是 p 的平方剩余 所以 1 p ap p a p 1 p a 2 1 1 p p a 即 p a 也是 p 的平方剩余 3 已知 p q 是两个不同的质数 且 ap 1 1 mod q aq 1 1 mod p 证明 apq a mod pq 证明 由 p q 是两个不同的质数知 p q 1 于是由 Fermat 定理 ap a mod p 又由题设 aq 1 1 mod p 得到 apq aq p ap aq 1 p ap a mod p 同理可证 apq a mod q 故 apq a mod pq 4 证明 若 m n 都是正整数 则 mn m n m n 证明 易知 mn 与 m n 有完全相同的质因数 设它们为 pi 1 i k 则 1 1 1 1 1 1 21k ppp mnmn 1 1 1 1 1 1 21k ppp nmnm 又 mn m n m n 故 1 1 1 1 1 1 21 nmnm ppp nmnmmn k 类似的题 设 m m1m2 m1与 m 由相同的质因数 证明 m m2 m1 初等数论练习题六 一 填空题 1 为了验明 2011 是质数 只需逐个验算质数 2 3 5 p 都不能整除 2011 此时 质 数 p 至少是 43 13 2 最大公因数 4n 3 5n 2 的可能值是 1 7 3 设 3 40 而 3 140 即 3 40 则 18 4 形如 3n 1 的自然数中 构成模 8 的一个完全系的最小那些数是 1 4 7 10 13 16 19 22 5 不定方程 x2 y2 z2 2 x x y 1 x y z 0 的整数解是且仅是 x 2ab y a2 b2 z a2 b2 其中 a b 0 a b 1 a 与 b 有不同的奇偶性 6 21x 9 mod 43 的解是 x 25 mod 43 7 1 199 73 二 计算题 1 将写成三个既约分数之和 它们的分母分别是 3 5 和 7 105 17 解 设 即 35x 21y 15z 17 因 35 21 7 7 15 753105 17zyx 1 1 17 故有解 分别解 5x 3y t 7t 15z 17 得 x t 3u y 2t 5u u Z t 11 15v z 4 7v v Z 消去 t 得 x 11 15v 3u y 22 30v 5u z 4 7v u v Z 令 u 0 v 1 得到 x 4 y 8 z 3 即 7 3 5 8 3 4 105 17 2 若 3 是质数 p 的平方剩余 问 p 是什么形式的质数 解 由二次互反律 3 1 3 2 1 p p p 注意到 p 3 p 只能为 p1 mod 3 且 1 1 3 p 4 mod1 4 mod1 p p 只能下列情况 1 3 p mod mod 41 31 p p 4 mod1 3 mod1 p p 或 mod121 p mod121 p 3 判断不定方程 x2 23y 17 是否有解 14 解 只要判断 x2 17 mod 23 是否有解即可 17 1 mod 4 1 3 2 3 17 17 3 17 3 17 2 17 6 17 23 23 17 x2 17 mod 23 无解 即原方程无解 三 论证题 1 试证对任何实数 x 恒有 x x 2x 2 1 证明 设 x x 0 1 当 0 时 x x 2x 2 x 等式成立 2 1 2 1 当 0 v 0 41 3v 2u 0 2 有一队士兵 若三人一组 则余 1 人 若五人一组 则缺 2 人 若十一人一组 则余 3 人 已知这队士兵不超过 170 人 问这队士兵有几人 解 设士兵有 x 人 由题意得 x 1 mod 3 x 2 mod 5 x 3 mod 11 在孙子定理中 取 m1 3 m2 5 m3 11 m 3 5 11 165 M1 55 M2 33 M3 15 M1 1 M2 2 M3 3 则 x 1 55 1 2 33 2 3 15 3 58 mod 165 因此所求的整数 x 52 165t t Z 由于这队士兵不超过 170 人 所以这队士兵有 58 人 3 判断同余方程是否有解 mod443286 2 x 解 286 2 143 433 是质数 143 443 1 奇数 143 不是质数 但可用判定雅可比符号计算的勒让德符号 143 7 143 2 143 14 143 443 1 1 443 143 243 2 443 286 2 1443 2 1143 2 14432 17 原方程有解 7 143 1 1 2 1143 2 17 8 1143 1 3 1 7 3 四 证明题 1 设 a m 1 d0是使 a d 1 mod m 成立的最小正整数 则 d0 m 对于任意的 i j 0 i j d0 1 i j 有 a ia j mod m 1 证明 由 Euler 定理 d0 m 因此 由带余数除法 有 m qd0 r q Z q 0 0 r d0 因此 由上式及 d0的定义 利用欧拉定理得到 1 mod m rrqdm aaa 0 即整数 r 满足 a r 1 mod m 0 r j 因为 a m 1 所以 ai j 0 mod m 0 i j 1 b m 1 并且 b a 1 mod m b c 1 mod m 1 记 d a c 则 bd 1 mod m 证明 由裴蜀恒等式知 存在整数 x y 使得 ax cy d 显然 xy 0 y 0 由式 1 知 1 b ax b db cy b d b c y b d mod m 若 x 0 由式 1 知 1 b cy b db ax b d ba x b d mod m 3 设 p 是素数 p bn 1 n N 则下面的两个结论中至少有一个成立 p bd 1 对于 n 的某个因数 d 2 则 中的 mod n 可以改为 mod 2n 证明 证明 记 d n p 1 由 b n 1 b p 1 1 mod p 及第 2 题有 b d 1 mod p 18 若 d 2 则 p 1 mod 2 由此及结论 并利用同余的基本性质 得到 p 1 mod 2n 初等数论练习题八 一 单项选择题 1 设 n 1 则 n 为素数是 n 1 1 mod n 的 C A 必要但非充分条件 B 充分但非必要条件 C 充要条件 D 既非充分又非必要条件 2 小于 545 的正整数中 15 的倍数的个数是 C C A 34 B 35 C 36 D 37 3 500 的标准分解式中 7 的幂指数是 D A 79 B 80 C 81 D 82 4 以下各组数中 成为模 10 的简化剩余系的是 D A 1 9 3 1 B 1 1 7 9 C 5 7 11 13 D 1 1 3 3 5 设 n 是正整数 下列选项为既约分数的是 A A B C D 2n5 1n3 1n2 1n 2n5 1n2 1n3 1n 二 填空题 1 120 360 2 7355的个位数字是 3 3 同余方程 3x 5 mod14 的解是 x 11 mod14 4 1 23 17 5 2 2 6 如果一个正整数具有 6 个正因数 问这个正整数最小是 12 7 同余方程 x3 x2 x 1 0 mod 5 的解是 x 1 mod5 三 计算题 1 已知 563 是素数 判定方程 x2 429 mod 563 是否有解 19 解 把看成 Jacobi 符号 我们有 563 429 429 67 1 429 67 429 2 429 134 429 563 429 563 1 563 429 8 1429 2 1563 2 1429 2 27 67 27 67 1 67 27 67 429 67 429 1 429 67 2 167 2 127 2 1429 2 167 1 13 1 13 27 1 27 13 2 113 2 127 故方程 x2 429 mod 563 有解 2 求出模 23 的所有的二次剩余和二次非剩余 解 模 23 的所有的二次剩余为 x 1 2 3 4 6 8 9 12 13 16 18 mod 23 模 23 的所有的二次非剩余为 x 5 7 10 11 14 15 17 19 20 21 22 mod 23 3 试求出所有正整数 n 使得 1n 2n 3n 4n 能被 5 整除 解 若 n 为奇数 则 1n 2n 3n 4n 1n 2n 2 n 1 n 0 mod 5 若 n 2m m Z 则 1n 2n 3n 4n 12m 22m 2 2m 1 2m 2 2 22m 2 2 4m 2 2 1 m mod 5 当 m 为奇数时 1n 2n 3n 4n 0 mod 5 当 m 为偶数时 1n 2n 3n 4n 4 mod 5 故当 4 n 时 5 1n 2n 3n 4n 四 证明题 1 证明 若质数 p 2 则 2P 1 的质因数一定是 2pk 1 形 证明 设q是 2 1 的质因数 由于 2 1 为奇数 q 2 2 q 1 pp 由条件 q 2p 1 即 2 1 mod q p 设 h 是使得 2 1 mod q 成立最小正整数 若 1 h 1 a m 1 x1 x2 x m 是模 m 的简化剩余系 求 1 m i i m ax 其中 x 表示 x 的小数部分 解 设 axi mqi ri 0 ri 3 p 只能为 p1 mod 4 且 1 1 3 p 3 mod1 3 mod1 p p 只能是下列情况 1 3 p 4 mod1 3 mod1 p p 4 mod1 3 mod1 p p 25 或 mod121 p mod121 p 2 求使 12347 被 35k整除的最大的 k 值 解 k 2054 四 证明题 1 证明 设是一个质数 则存在唯一的一个正整数 x 使得 7p 1 2 1 0 modxpxp 且120p 6 证明 存在性 因为是一个素数 由