王进明--初等数论-习题解答

王进明王进明 初等数论初等数论 习题及作业解答习题及作业解答 P17 习题 1 1 1 2 2 3 3 7 11 12 为作业 1 已知两整数相除 得商 12 余数 26 又知被除数 除数 商及余数之和 为 454 求被除数 解 1226 1226454 abab 12261226454 bb b 30 被除数a 12b 26 360 26 386 12 1 454 122626390 b 这题的后面部分是小学数学的典型问题之一 和倍 问题 2 证明 1 当 n Z 且时 r 只可能是 0 1 8 3 9 09 nqrr 证 把 n 按被 9 除的余数分类 即 若 n 3k k Z 则 r 0 33 27nk 若 n 3k 1 k Z 则 r 1 3322 3 3 3 3 3 19 331 1nkkkkkk 若 n 3k 1 k Z 则 r 8 33232 3 3 3 3 3 19 331 8nkkkkkk 2 当 n Z 时 的值是整数 32 326 nnn 证 因为 只需证明分子是 6 的倍数 32 326 nnn 32 23 6 nnn 32 23nnn 322 23 231 1 21 nnnnnnnnn 1 21 nn nn 1 2 n nn 1 1 nn n 由 k 必整除 k 个连续整数知 6 6 1 2 n nn 1 1 nn n 或证 2 必为偶数 故只需证 3 1 nn 1 nn 1 21 nnn 若 3 n 显然 3 若 n 为 3k 1 k Z 则 n 1 是 3 的倍数 得知 1 21 nnn 为 3 的倍数 若 n 为 3k 1 k Z 则 2n 1 2 3k 1 1 6k 3 2n 1 1 21 nnn 是 3 的倍数 综上所述 必是 6 的倍数 故命题得证 1 21 nnn 3 若 n 为非负整数 则 133 11n 2 122n 1 证明 利用 11n 2 122n 1 121 11n 12 144 n 133 11n 12 144 n 11 n 及例 5 的结论 4 当 m n l N 时 的值总是整数 mnl m n l 证明 mnl 1 1 1 1 mnl mnlnlnl nlll 由 k 必整除 k 个连续整数知 1 1 mmnl mnlnl n 从而由和的整除性即证得命题 1 1 nl nll 5 当 a b Z 且 a b n 是双数时 nn abab 6 当 a b Z 且 a b n 是单数时 nn abab 解 利用例 5 结论 若 a b 则 令 b b 即得 nn abab 或解 a a b b 5 当 n 为双数时 由二项式展开 n nnn ababbb 证得 6 当 n 为单数时类似可 11 1 1 nnn n abn abbn ab b 得 3 已知 a1 a2 a3 a4 a5 b Z 且 说明这六个数不能都是奇数 5 22 1 i i ab 解 若这六个数都是奇数 设 则21 1 2 3 4 5 iii akkZ i 因为 所以 8 4 555 22 111 21 4 1 5 iiii iii akk k 2 1 ii k k 5 1 1 ii i k k 而 5 2 1 85 i i aqqZ 22 21 4 1 1bkk k 2 81bq k qZ 即等式左边被 8 除余 5 而右边被 8 除余 1 故不可能这六个数都是奇数 4 能否在下式的各 内填入加号或减号 使下式成立 能的话给出一种填法 否则 说明理由 1 2 3 4 5 6 7 8 9 10 不能 因为等式左边有单数个单数 它们的和差只能是奇数 而等式右边 10 为偶数 或解 无论各 内填入加号或减号 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 总 是偶数 而 1 2 3 4 5 6 7 8 9 45 因此的结果 1 2 3 4 5 6 7 8 9 一定是奇数 5 已知 a b c 均为奇数 证明无有理根 2 0axbxc 证 若有有理根 记为互质 代入方程有 p p q q 2 0 pp abc qq 即 这是不可能的 因为 p q 互质 二者不可能同时为偶数 22 0apbpqcq 若 p 为偶数 则为偶数 但是奇数 它们的和不可能为 0 2 apbpq 2 cq 若 q 为偶数 则为偶数 但是奇数 它们的和也不可能为 0 2 bpqcq 2 ap 6 在黑板上写出三个整数 然后擦去一个 换成其他两数之和加 1 继续这样操作下 去 最后得到三个数为 35 47 83 问原来所写的三个数能否是 2 4 6 解 不能 因为原来所写的三个数若是 2 4 6 每次操作后剩下的三个数是两偶一 奇 7 将 1 99 这 99 个自然数依次写成一排 得一多位数 A 1 2 3 4 5 6 7 8 9 1011 97 98 99 求 A 除以 2 或 5 4 或 25 8 或 125 3 或 9 11 的余数分别是多少 解 由数的整除特征 2 和 5 看末位 A 除以 2 余 1 A 除以 5 余 4 4 和 25 看末 两位 A 除以 4 余 3 A 除以 25 余 24 8 和 125 看末三位 A 除以 8 余 3 且除以 125 余 24 3 和 9 看各位数字的和 1 2 3 4 5 6 7 8 9 45 A 所有数字的和等于 450 A 除以 3 和 9 都余 0 A 除以 11 的余数利用定理 1 4 计算奇数位数字之和 A 的偶数 位数字之和 奇数位数字之和 1 3 5 7 9 0 1 9 9 偶数位数字之和 2 4 6 8 1 2 9 10 两者之差为 40 原数除以 11 的余数就是 40 除以 11 的余数 4 8 四位数 7x2y 能同时被 2 3 5 整除 求这样的四位数 解 同时被 2 5 整除 个位为 0 再考虑被 3 整除 有 4 个 7020 7320 7620 7920 9 从 5 6 7 8 9 这五个数字中选出四个不同的数字组成一个四位数 它能同时被 3 5 7 整除 那么这些四位数中最大的一个是多少 被 5 整除 个位必为 5 5 6 7 8 26 5 6 7 9 27 5 6 8 9 28 5 7 8 9 29 中唯 27 能 被 3 整除 故选出的四个不同的数字是 5 6 7 9 但不同排序有 9765 9675 7965 7695 6975 6795 从最大的开始试除 得 9765 7 1395 那么要求的就是 9765 了 10 11 1 至 1001 各数按以下的格式排列成表 像表中所示的那样用 个正方形框住其中 的 9 个数 要使 9 个数的和等于 1 2001 2 2529 3 1989 能否办到 如能办到 写出框 里的最小数与最大数 如办不到 说明理由 1234567 891011121314 15161718192021 22232425262728 99599699799899910001001 解 设框里居中心的数为 x 则 9 个数的和等于 9x 1 9 不能整除 2001 和等于 2001 办不到 2 9x 2529 x 281 是所在行第一个数 和等于 2529 办不到 3 9x 1989 x 221 和等于 1989 能办到 框里的最大数为 x 8 229 最小数为 x 8 213 12 证明 7 或 11 或 13 的特征是 7 或 11 或 13 整除 13210 nn a aa a a a 13210 nn a aaa a a 解答 因为 7 11 13 1001 谐 一千零一夜 anan 1 a3a2a1a0 7 11 13 a2a1a0 anan 1 a3 a2a1a0 1000 附 广西师范大学 赵继源主编的 初等数论 习题 1 1 中的部分题目 3 已知 a b c 中 有一个是 2001 有一个是 2002 有一个是 2003 试判断 a 1 b 2 c 3 的奇偶性 并说明理由 6 24 62742 求 9 是否存在自然数 a 和 b 使 a2 b2 2002 成立 11 证明 当 n Z 时 6 n n 1 2n 1 12 已知 f 0 f 1 f 1 x 均为整数 证明 2 f xaxbxc f xZ 解答 3 偶数 因为 a b c 中 有三个奇数 所以 a 1 c 3 中至少有一个是偶数 6 只需 即 先考虑3 62742 8 62742 且3 8 且 有 5 组解 0 2 4 6 8 0 2 4 7 9 0 4 8 2 6 9 不存在 利用 a2 b2 a b a b 而 a b a b 的奇偶性相同 而 2002 2 1001 11 用数学归纳法或 n n 1 2n 1 n n 1 n 2 n 1 n n 1 利用整除的基本性质 13 12 由 f 0 f 1 f 1 x 均为整数可得 c a b a b 均为整数 进而知 2a 2b 为整数 分类讨论 k Z x 2k 时 由 2a 2b 为整数 f x 显然为整数 x 2k 1 时 f 2k 1 4ak k 1 2bk a b c 可知 f x 仍然为整数 习题 1 2 1 判断下列各数中哪些是质数 109 2003 17357 2 求证 对任意 n Z 必有 n 个连续的自然数都是合数 3 当 n 是什么整数时 n4 n2 1 是质数 4 求证 当 n Z 时 4n3 6n2 4n 1 是合数 5 求 a 使 a a 4 a 14 都是质数 6 已知两个质数 p 和 q 满足关系式 3p 5q 31 求 p 3q 1 的值 7 已知 p 3 且 p 和 2p 1 都是质数 问 4p 1 是质数还是合数 8 由超级计算机运算得到的结果 2859433 1 是一个质数 试问 2859433 1 是质数还 是合数 请说明理由 9 已知 质数 p q 使得表达式 2p 1 q 及 2q 3 p 都是自然数 求 p q 的值 10 试证 形如 4n 1 的数中包含有无穷多个质数 11 1 若 n 是合数 证明 2n 1 也是合数 2 有人认为下列各和数 1 2 4 1 2 4 8 1 2 4 8 16 交替为质数与合数 你认为对吗 12 已知 质数 p 5 且是质数 证明 4p 1 必是合数 习题 1 2 解答 1 109 用质数试除到 7 2003 用质数试除到 37 可知两者是质数 10911 200345 17357 17 1021 是合数 试除时 用数的整除特征考虑 2 3 5 显然不能整除它 由 上节第 8 题结论 357 17 340 340 不能被 7 11 13 整除 再用 17 考虑 得分解 式 2 为作一般性证明 可如下构造 n 个连续自然数 n 1 2 n 1 3 n 1 n 1 显然它们每个都是合数 3 利用 n4 n2 1 n4 2n2 1 n2 n2 n 1 n2 n 1 知仅当 n 1 时 n4 n2 1 为质 数 4 利用 4n3 6n2 4n 1 2n 1 2n2 2n 1 n Z n 1 2n 1 和 2n2 2n 1 皆为大于 1 的数 5 a 3 思路 分类讨论 k Z a 3k 1 时 a 14 是 3 的倍数 a 3k 2 时 a 4 是 3 的倍数 必有 a 3k 即 a 为 3 的倍数 而 a 是质数 只有 a 3 时 三个数全是质数 6 条件为一个不定方程 可知 1 3 得 p 不是 3 的倍数 p 3k 1 3 2p 1 所以 p 3k 2 3 4p 1 或解 4p 4p 1 4p 2 是三个连续整数 必有一个被 3 整除 由题设 只有 3 4p 1 8 合数 2859433不可能是 3 的倍数 连续三个自然数中必有一个是 3 的倍数 即 2859433 1 另一种解法 由习题 1 1 第 1 题 2 的结论 2 1 2859433 1 9 设 h k 必为奇数 而 2123 pq hk qp 21424242 4 23 pppp k qqkpkp 得 k 不能为 3 故只有 k 1 这样 2q 3 p 代入 同时质数 p q 大于 3 所以 45 4 q h q 只能有 h 3 因而得 q 5 p 7 10 先证 一切大于 2 的质数 不是形如 4n 1 就是形如 4n 1 的数 再证任意多个形 如 4n 1 的数 最后用数学归纳法验证 若形如 4n 1 的质数只有有限个 p1 p2 pk 令 N 4 p1 p2 pk 1 N 为形如 4n 1 的数 由假设 N 必为合数 且必有一个形如 4n 1 的质因数 p 为什么 因此 p 为 p1 p2 pk中在某一个 于是 p 1 矛盾 11 1 n 是合数 设 n st 2n 1 2st 1 2s 1 2s t 1 2s t 2 2s 1 2 1 2 22 2n 1 2n 1 当 n 14 15 时 214 1 215 1 均为合数 不对 12 书后提示说取模为 6 分类讨论 p 即设 p 6q r r 0 1 2 3 4 5 由质数 p 5 若 p 6q 6q 2 6q 3 或 6q 4 p 皆为合数 不可能 若 p 6q 1 则 2p 1 12q 3 也是合数 故在题设条件下 只有 p 6q 5 此时 4p 1 24q 21 是合数 实际上 这题与第 7 题完全相同 质数 p 3 质数 p 5 可用前面的方法简单求解 习题 1 3 1 求 1 21n 4 14n 3 其中 n Z 2 30 45 84 30 45 84 3 5767 4453 2 求证 an bn a b n a b n Z 3 自然数 N 10 x y x 是非负整数 y 是 N 的个位数字 求证 13 N 的充要条件是 13 x 4y 4 用割 尾 减法判断下列各数能否被 31 41 51 整除 26691 1076537 1361241 5 有 15 位同学 每位同学都有编号 他们是 1 号到 15 号 1 号同学写了一个自然数 2 号说 这个数能被 2 整除 3 号说 这个数能被 3 整除 依此下去 每位同学都说这 个数能被他的编号整除 1 号做了一一验证 只有编号连续的两位同学说的不对 其余同 学都对 问 1 说得不对的两位同学的编号是什么数 2 如果 1 号写的数是 5 位数 这个 5 位数是多少 6 请填出下面购物表格中 内的数字 品名数量单价 元 总价 元 课桌72 7 7 课椅77 3 合计金额 元 3 55 7 狐狸和黄鼠狼进行跳跃比赛 狐狸每次跳 4 12 米 黄鼠狼每次跳 2 34 米 它们每秒钟 都只跳一次 比赛途中 从起点开始 每隔 12 38 米设有一个陷阱 当它们之中有一个掉 进陷阱时 另一个跳了多少米 8 大雪后的一天 大亮和爸爸共同步测一个圆形花圃的周长 他俩的起点和走的方向完全 相同 大亮每步长 54 厘米 爸爸每步长 72 厘米 由于两人脚印有重合 所以雪地上只留 下 60 个脚印 求花圃的周长 9 设 a b 是自然数 a b 33 a b 90 求 a b 10 一公路由 A 经 B 到 C 已知 A B 相距 280 米 B C 相距 315 米 现在路边植 树 要求相邻两树间的距离相等 并要求在 B 点 AB BC 的中点上都要植上一棵树 那么两树间的距离最多有多少米 11 一袋糖不足 60 块 如果把它平均分给几个孩子 则每人恰好分得 6 块 如果只分给 这几个孩子中的男孩 则每个男孩恰好分得 10 块 这几个孩子中有几个女孩 12 爷爷对小明说 我现在的年龄是你的 7 倍 过几年是你的 6 倍 再过若干年就分别 是你的 5 倍 4 倍 3 倍 2 倍 你知道爷爷和小明现在的年龄吗 习题 1 3 解答 1 1 1 用辗转相除法 2 1260 3 73 用辗转相除法 2 证 1 14 nnnn nnn nn nnnn abab a ba ba ba b a ba ba ba b 由定理 而由定理 1 13 从而由定理 1 21 推论 3 1 1 ab a ba b nn ab a ba b an bn a b n 再由定理 1 19 a b a b a b 等式两边同时 n 次方 得 a b n a b n a n b n 同样由定理 1 19 an bn an bn an bn a b n a b n an bn an bn a b n an bn 3 利用 10 x y 10 x 4y 39y 4 31 26691 41 26691 51 26691 31 1076537 41 1076537 51 1076537 31 1361241 41 1 361241 51 1361241 以 51 为例 51 26691 51 2669 1 5 又 51 2664 51 266 4 5 显然 51 246 51 1361241 51 136124 1 5 又 51 136119 51 13611 9 5 又 51 13566 51 1356 6 5 又 51 1326 51 132 6 5 而 51 102 5 1 这两个连续的编号的倍数应该大于 15 否则编号是它们的倍数的同学说的也不对 而且是这两个连续的编号的质因数的次数应该高于比它小的数 否则编号是它们的质因数 的同学中至少也有一个说的也不对 因此只能是 8 9 2 60060 因为 1 号写的数是 2 到 15 除 8 9 之外的整数的公倍数 也就是 3 4 5 7 11 13 的公倍数 3 4 5 7 11 13 两两互质 它们的最小公倍数 60060 就是 5 位数 6 72 8 9 8 9 互质 故总价必为 8 9 的倍数 可推得为 707 76 元 因而知课桌的单价 为 9 83 元 课椅的总价为 3 79 元 由 77 7 11 推得另两个数字 即课椅总价为 328 79 元 再得课椅单价为 4 27 元 合计金额为 1036 55 元 7 黄鼠狼 4500 1237549500 2750 1237524750 247502475027509 较小 在第 9 跳掉进陷阱 此时狐狸跳了 4 5 9 40 5 米 8 54 72 216 每 216 厘米有脚印6 个 故花圃的周长 2160 厘米 216216 1 5472 9 此题应该先讨论 a b a b 与 a b 的关系 121212122 122121121 2121 121 2 1 1 1 1 1 1 1 21 1 14 a bd adt bdtt tx yxtytx ttyx t tt ttt ttt t ttt t dtdt dt tda bab a b 令使 同理定理 定理即 33 90 3 所以 a b 3 10 因为 AB BC 的中点上都要植上一棵树 315 2 157 5 因此应考虑 1400 和 1575 的最 大公约数 175 最后答案 两树间的距离最多有 17 5 米 11 2 个 12 设小明 x 岁 则爷爷 7x 岁 7x h 6 x h x 5h 7x k 5 x k x 2k 7x i 4 x i x i 7x j 2 x j 5x j 知小明年龄是 2 5 的倍数 因此小明 10 岁 爷爷 70 岁 习题 1 4 1 把下列各数分解质因数 2001 26840 111111 2 将 85 87 102 111 124 148 154 230 341 354 413 667 分成两组 每组 6 个数 怎么分才能使每组各数的乘积相等 3 要使下面四个数的乘积的最后 4 个数字都是 0 括号中最小应填什么自然数 975 935 972 4 用分解质因数法求 1 4712 4978 5890 2 4712 4978 5890 5 若 2836 4582 5164 6522 四个数被同一个自然数相除 所得余数相同 求除数和余 数各是多少 6 200 以内仅有 10 个正约数的自然数有几个 并一一求出 7 求 1 180 2 a 2 b 5 a 2 b 7 a 3 b 2 a 2 b 11 得 48 80 112 162 176 7 1 18 2 546 3 180 8 因为 B B 所以 B 是 66 42 的公约数 因而 B 是 6 的约数 又 B C A B 所以 7 A 11 C 从而设 662 3 11 422 3 7 B CA B 因为 由因为 121212 2 3 7 2 3 2 3 11 ABC 221 3 1 1A C 知且 若 B 不含 2 的话 由 A C 就必须同时含 2 与矛 66 42B CA B 3A C 盾 121 12111 23 7 2 3 23 11 1 0 1 ABC 而且与不能同时为 于是共得 6 组 2111111 101 0 0 0 0 1 和时 各有三种情况 解 分别为 9 576 和 162 10 3535 本 解 由题目可知小明的书的册数是 35 的倍数 设为 35k 可列出方程 28k 5xk 28 5x k 303 3 101 知 k 101 11 分解质因数 884 4 13 17 17 52 68 13 884 的因数中有 4 13 52 都具有 3k 1 形式 只有 52 符合 50 人左右的题设 因此学生 51 人 12 灯的一次 改变 对应着它的编号的一个因子 要使灯仍旧亮着需要奇数次 改变 什么 样的数有奇数个因子呢 由定理 1 26 公式 知只有完全平方数 200 以内的完全平方数 只有 14 个 即为答案 此题也可先考虑 10 个灯泡 用归纳得出 只有完全平方数 的结 论 习题 1 6 部分习题解答 2 代入得 10 1373771 273 2 2 22237 ab 3 若 1 2x yRxyxyxyxy 求证 试讨论与的大小关系 证 1xyxxyyxyxyxyxy 0 xyxyxy 显然 证得 20 1 2 2 1 2 52 0 52 0 02 1 9 1 8 3 42 0 42 0 72 xyZxyxyxyxy xyxyxyxyxyxy xyxyxyxyxyxy 时 有 而 时 又 时 可见 三种情况都有 4 解方程 1 35500 xx 解 503550 53 xy xyx 是整数 设其为由原方程得 503850850 01 555 xxx xxx 又 5055 08505 88 xx 即 505505561 1314 83888 y y 亦即14y 20 3 x 2 原式化为 整理后再由一元二次方程求根公式得 2 0 xx xx 与相乘后的积为整数 只能是 51 2 xx 51 2 51 2 x 5 15 x y 16 6 25 222 310 56 73 112 13 17 19 23 由定理 1 29 公式求出各个质数的指数 7 1 199 1199 2199 96 979797 解 5 15 25 96 2 12 22 96 979797 原式 5 15 25 96 2 12 22 96 979797 5 15 195 205 385 395 58 9312 979797979797 5 785 96 9797 9312 0 0 19 40 57 76 9504 2 222 111 1 232008 考虑 111 1 1 22 32007 2008 111111 1 122320072008 从而 1 222 1111 1 122 2320082008 222 111 1 232008 8 1373 个 9 14 人 10 49 盏 11 21 11211 21 x xxxx x 高中时我们已知 12 21xxx 时 112 010 220 2 xxxxxxxZ 时 即即而 12 23 xxx 时 1 0 2 xx 2 x 1 或 2 x j 时 2i 2j 2j 2i j 1 112j 通过验证可知 对任何 i j 也有 11 2i j 1 11 10 而 20 21 22 29为 10 个不同的整数 所以它们构成模 11 的一个简化剩 余系 2 列表求出模 m 为 10 11 12 18 等值时的最小简化剩余系及相应的 m m最 小 简 化 剩 余 系 m 1013794 111234567891010 12157114 131234567891011121215124781113148 16135791113158 171234567891011121314151616 181571113176 3 证明定理 2 7 证明 必要性 x1 x2 xk是模 m 的简化剩余系 k m 且当 i j 时 xixj mod m xi m 1 i 1 2 m 充分性 k m x1 x2 xk共有 m 个 又 xixj mod m i j 1 i j k xi m 1 i 1 2 k x1 x2 xk各属于 m 个不同的且与 m 互质的剩余类 x1 x2 xk是模 m 的简化剩余系 4 验证 1 8 16 24 32 40 48 是模 7 的简化剩余系 2 11 13 77 99 是模 10 的简化剩余系 解 1 4 7 1 可化为 2 4 6 8 5 12 又 5 12 mod 7 8 16 24 32 40 48 不是模 7 的简化剩余系 2 10 的最小简化剩余系是 1 3 7 9 11 13 77 99 分别与 1 3 7 9 关于模 10 同 余 11 13 77 99 是模 10 的简化剩余系 5 当 m 取下列各值时 计算 m 的值 25 32 40 48 60 120 100 200 4200 9450 答案 25 20 32 16 40 16 48 16 60 16 120 32 100 40 200 80 4200 960 9450 2160 6 若 m 是奇数 试求 m 的值 解 参看下一题 m 1 或 m 2 7 当 m 2 时 证明 m 是偶数 证 设 m p1 1p2 2 pk k m 2 至少存在 i i 1 或存在 j pj是奇数 p1 1 p1 1 1 pk k pk k 1中至少有一个为偶数 知 m 必为偶数 或证 11 1 1 iiiii ppppp iii i 若有无论为奇为偶 有 是偶数 1 1 1 i i pm mmmm p i 所有的则必有一个为奇数 因为如果为质 数 大于2的质数是奇数 是偶数 如果为 合数 中最多只有一个是2 偶数 那么至少有一个为奇数 1 1 k i i mp 这时显然是偶数 8 试证 使 m 14 的数 m 不存在 证 m 14 2 7 p1 1 1 pk k 1 p1 1 pk 1 2 7 是质数 所以必有 p1 2 p1 7 这 是不可能的 9 已知 m 4 求 m 解 设 m p1 1p2 2 pk k 由 m p1 1 p1 1 1 pk k pk k 1 m 4 4 1 22 得 m 5 m 5 1 4 或 m 8 23 m 22或 m 10 5 2 m 4 1 或 m 12 10 如果 n 2m 2 m 1 那么 n m 11 若 m 是奇数 则 4m 2 m 12 1 分母是正整数 n 的既约真分数的个数是多少 为什么 2 分母不大于 n 的既约真分数的个数是多少 为什么 解 10 2 m 1 n 2m 2 m m 11 m 是奇数 4 m 1 则 4m 4 m 4 2 4m 2 m 12 1 n 2 2 3 n 习题 2 4 1 举例说明欧拉定理中 a m 1 是不可缺少的条件 2 求下列各题的非负最小余数 1 84965除以 13 2 541347除以 17 3 477385除以 19 4 7891432除以 18 5 127156 34 28除以 111 解答 1 当 a 2 m 4 时 4 2 此时 22 0 mod 4 可见 a m 1 是欧拉定 理的不可缺少的条件 2 1 8 2 10 3 16 4 1 5 70 1 84965除以 13 13 8 1 812 1 mod 13 84965 812 413 89 1 1 4 8 mod 13 或解 82 1 mod 13 84965 82 2482 8 1 2482 8 8 mod 13 3 设 p q 是两个大于 3 的质数 求证 p2 q2 mod 24 4 设 p 是大于 5 的质数 求证 p4 1 mod 240 解答 3 24 3 8 3 8 1 由条件 p 3 q 3 1 由费尔马小定理有 p2 1 mod 3 q2 1 mod3 p2 q2 mod 3 又 p q 必为奇数 由习题 2 1 第 9 题的结论 有 p2 1 mod 8 q2 1 mod8 p2 q2 mod 8 p2 q2 mod 24 4 240 3 5 16 由条件 p 3 p 5 1 p4 1 mod5 p4 p2 2 1 mod3 又 p 为奇质数 从而 2 p2 1 8 p2 1 16 p4 1 即 p4 1 mod 16 而 3 5 3 16 5 16 1 p4 1 mod 240 5 已知 p 是质数 a p 1 求证 1 当 a 是奇数时 ap 1 p 1 a 0 mod p 2 当 a 是偶数时 ap 1 p 1 a 0 mod p 6 已知 p q 是 两 相 异 的 质 数 且 ap 1 1 mod q aq 1 1 mod p 求证 apq a mod pq 解答 5 1 由 p 是 质 数 a p 1 a 为 奇 数 有 ap 1 1 mod p p 1 a 1 mod p ap 1 p 1 a 1 1 0 mod p 2 由条件 ap 1 1 mod p p 1 a 1 mod p ap 1 p 1 1 1 0 mod p n 6 ap a mod p apq ap q aq a mod p 同理 apq aq p ap a mod q 而 p q 1 故 apq a mod pq 7 如果 a m 1 x ba mod m 那么 ax b mod m 1m 8 设 A 是十进制数 44444444的各位数字之和 B 又是 A 的各位数字之和 求 B 的各位 数字之和 9 当 x Z 时 求证 1 2730 x13 x 2 24 x x 2 25x2 1 解答 7 x ba mod m ax aba ab mod m a m 1 a 1 1m 1m m m mod m ax b mod m 8 设 B 的各位数字之和为 C lg44444444 4444lg4444 4444 4 17776 即 44444444 的位数小于 17776 A 9 17776 159984 B 3 x Z 试证 6p xp x 11 p 是不等于 2 和 5 的质数 k 是自然数 证明 19 9999 pp p 个 解答 10 质数 p 3 6 p 1 xp x x xp 1 1 0 mod p 又 p 1 是偶数 x xp 1 1 x x2 1 mod p 于是 当 2 x 或 2 x 时 x x2 1 0 mod 2 当 3 x 或 3 x 时 x x2 1 0 mod 3 故 x xp 1 1 0 mod 6 从而 6 p xp x 11 由条件 10 p 1 10p 1 1 mod p 1 19 9999101 pk pk 个 10p 1 k 1 mod p 19 9999 pp p 个 12 设 m n 1 证明 m n 1 mod mn n m 证 m n 1 n 1 mod m 而 m 0 mod m m n m n n m 1 mod m 对称可得 m n 1 mod n m n 1 mod mn n m n m 13 已知 a 18 m 77 求使 ax 1 mod m 成立的最小自然数 x x 30 由定理 满足要求的最小自然数 x 必为 60 的约数 验算可 77 11 1 7 160 知 习题 3 1 1 解下列不定方程 1 7x 15y 31 2 11x 15y 7 3 17x 40y 280 4 525x 231y 42 5 764x 631y 527 6 133x 105y 217 解 1 辗转相除得 15 7 2 1 1 15 7 2 7 2 15 1 因此原方程的一个解是 x0 2 31 62 y0 1 31 31 原方程的通解为 62 15 31 7 xt t yt 这里为任意常数 2 辗转相除得 15 11 1 4 11 4 2 3 4 3 1 1 4 3 4 11 4 2 4 3 11 15 11 1 3 11 15 3 11 4 因此原方程的一个解是 x0 4 7 28 y0 3 7 21 原方程的通解为 28 15 21 11 xt t yt 这里为任意常数 3 用分离整数法 2804086 162 1717 yy xy 观察可知 y 10 时 x 36 4 40 原方程的通解为 4040 10 17 xt t yt 这里为任意常数 2 解下列不定方程 1 8x 18y 10z 16 2 4x 9y 5z 8 3 39x 24y 9z 78 4 4x 10y 14z 6t 20 5 7x 5y 4z 3t 51 3 解下列不定方程组 1 x 2y 3z 10 2 5x 7y 3z 25 x 2y 5z 4 3x y 6z 2 3 4x 10y z 6 4 10 x 7y z 84 x 4y z 5 x 14y z 60 4 求下列不定方程的正整数解 1 5x 14y 11 2 4x 7y 41 3 3x 2y 8z 21 5 21 世纪有这样的年份 这个年份减去 22 等于它各个数字和的 495 倍 求这年份 6 设大物三值七 中物三值五 小物三值二 共物一百三十八 共值一百三十八 问物大 中小各几何 7 买 2 元 6 角钱的东西 要用 1 元 5 角 2 角 1 角的四种钱币去付 若每种钱币都得用 则共有多少种付法 8 把 239 分成两个正整数之和 一个数必是 17 的倍数 另一个数必是 24 的倍数 求这 两位数 9 一个两位数 各位数字和的 5 倍比原来大 10 求这个两位数 10 某人 1981 年时的年龄恰好等于他出生那一年的年号的各位数字之和 这个人是在哪一 年出生的 11 一个四位数 它的个位数上数比十位数字多 2 且此数与将其数字首尾颠倒过来所得 的四位数之和为 11770 求此四位数 习题 3 2 1 求 x2 y2 z2中 0 z y z 0 使 x y y z x z 都是平方数 1 b11122234 a24635745 x315355214579 y48121220282440 z517371329532541 2 设 x y a2 y z b2 x z c2 则 a2 b2 c2 因此给出 a b 的值即可求得 x y z 3 已知直角三角形斜边与一直角边的差为 9 三边的长互质且和小于 88 求此直角三角形 的三边的长 4 试证 不定方程 x4 4y4 z2没有正整数解 3 设直角三角形的三边的长为 x y z 则由定理 x a2 b2 y 2ab z a2 b2 由题目得 a2 b2 a2 b2 9 或 a2 b2 2ab 9 前者无整数解 后者 a b 2 9 a b 3 a 4 b 1 则 x 15 y 8 z 17 或 a 5 b 2 则 x 21 y 20 z 29 a 7 b 4 则三边的长的和大于 88 4 因为 z4 x4 4y4 2 x8 8x4y4 16y8 x4 4y4 2 2xy 4 即 2xy 4 z4 x4 4y4 2 就是说 如果 x4 4y4 z2有正整数解 则 u4 v4 w2有正整数解 与已证定理矛盾 故无正整数解 5 试证 每个正整数 n 都可以写为 n x2 y2 z2 这里 x y z 都是整数 6 求方程 x2 dy2 1 当 d 0 d 1 d 1 时的非负整数解 7 试证 2x2 y2 3z2 10t2无正整数解 5 适当取正整数 x 使 n x2 m 为一正奇数 设 y m 12 因为 y2 m m 1 22 z2 得 n x2 y2 z2 6 当 d 0 时 x 1 y 为任意非负整数 当 d 1 时 x 1 y 0 和 x 0 y 1 当 d 1 时 x 1 y 0 7 y2 3z2是偶数 y 与 z 必同奇同偶 若 y 与 z 同为奇数 则 2x2 y2 3z2被 8 除和 10t2被 8 除的余数不相等 故 y 与 z 一定同为偶数 令 y 2y1 z 2z1 代入原式得 x2 2y21 6z21 5t 同样 x 和 t 同奇同偶 也同样排除 x 和 t 同奇 令 x 2x1 t 2t1 代 入得 2x21 y21 3z21 10t21 由于 0 t1 t 矛盾 从而得证 习题 3 3 1 求不定方程 4x2 4xy 3y2 21 的正整数解 2 求不定方程 x2 y2 170 的正整数解 3 求不定方程 x2 18xy 35 0 的正整数解 4 求 4x2 2xy 12x 5y 11 0 的正整数解 5 求 x2 xy 6 0 的正整数解 6 求 y x 3y x 2 1 的正整数解 7 设 n 7 mod 8 则 n 不能表示为 3 个平方数的和 1 由 4x2 4xy 3y2 21 得 2x y 2x 3y 21 得 2x y 21 2x y 7 即 x 8 x 3 2x 3y 1 2x 3y 3 y 5 y 1 2 由 x2 y2 170 知 x y 同为奇数或同为偶数 x y 为偶数 则 x2 y2有因数 4 而 170 无 4 因数 x y 为奇数 设 x 2k 1 y 2h 1 代入化简得 k k 1 h h 1 42 仅当 k 0 h 6 或 k 0 h 6 时可求得 1 13 7 11 13 1 11 7 xxxx yyyy 3 x2 18xy 35 0 得 18y x 是 35 的约数 得 x 1 y 2 或 x 35 y 2 35x x 4 由原方程变为 y 2x 1 2x 5 是 6 的约数 1 2 3 6 通过分析得 6 25x x 3 y 11 或 x 4 y 9 5 x 1 y 51 或 x 2 y 11 6 原方程变形为 y 2 4x 1 可求得 x 2 3 5 代入可求 y 7 x2 y2 z2 n 7 mod 8 则 x y z 必有一奇数 由 x2 1 mod 8 有 y2 z2 6 mod 8 即 y z 同奇同偶 同奇不成立 同为偶时 由 y 4 mod8 产生矛 盾 8 x2 y2 p 3 mod4 当 x y 0 1 2 mod4 时 x2 y2 0 1 2 mod 4 这产生矛盾 命题得证 9 由原方程组中 x y z 0 得 z x y 代入 x3 y3 z3 18 则 xy x y 6 故 xyz 6 x y z 都是 6 的约数 并且只有一个是负数 可得其整数解 x 3 y 2 z 1 10 通过证明 x2 y2 z2被 8 整除所得的余数不等于 1 即可 11 通过证明 x3 y3 z3被 9 整除所得的余数不等于 4 即可 习题 4 2 P138 1 试写出三个模数是 18 的一次同余式 分别使它有唯一解 无解 有四个解 2 下列同余方程是否有解 为什么 如果有解 有多少个解 1 8x 5 0 mod 23 2 15x 7 0 mod 12 3 34x 0 mod 51 4 30 x 18 mod 114 5 174x 65 mod 1309 3 用同解变形法解下列同余方程 1 3x 2 mod 7 2 9x 12 mod 15 3 15x 9 mod 6 4 20 x 44 mod 72 5 40 x 191 0 mod 6191 6 256x 179 mod 337 4 用化为不定方程的方法解下列同余方程 1 20 x 4 mod 30 2 64x 83 mod 105 3 57x 87 mod 105 4 4x 11 mod 15 5 47x 89 mod 111 6 10 x 22 mod 36 5 利用欧拉定理解下列同余方程 1 6x 22 mod 36 2 3x 10 mod 29 3 258x 131 mod 348 4 11x 7 mod 13 5 3x 2 mod 17 6 243x 102 mod 551 6 用求组合数的方法解下列同余方程 1 5x 13 mod 43 2 9x 4 mod 2401 习题4 3 P154 第 2 题 a 取什么值时 下面的同余方程组有解 解 因为 18 21 3 3 8 5 所以有解 18 35 1 所以 5 mod18 8 mod 21 x x 总是有解 因此 要使题设的同余方程组有解 只需 5 mod18 mod 35 x xa 有解 mod 35 8 mod 21 xa x 而这里 21 35 7 由定理可知 只需 a 8 1 mod 7 即 x 1 7t t 为整数 题设的同余方程组总有解 3 解下列同余方程组 1 2 3 mod 7 5 mod11 x x 6 mod13 7 mod 24 x x 4 5 57 mod11 690 mod19 x x 24 mod 8 155 mod 35 x x 解 1 方法一 设 x 5 11y 代入第一个同余方程 得 11y 3 5 mod 7 得 y 3 mod 7 所以同余方程组的解是 x 38 mod 77 方法二 用孙子定理解 M 77 M1 11 M2 7 令 11 M1 1 mod 7 得 M1 2 mod 7 7 M2 1 mod 11 得 M2 3 mod 11 所以同余方程组的解是 x 11 2 3 7 3 5 39 38 mod 77 2 方法一 设 x 7 24y 代入第一个同余方程 得 24y 6 7 mod 13 得 y 7 mod 13 所以同余方程组的解是 x 7 24 7 175 mod 312 方法二 用孙子定理解 M 312 M1 24 M2