习题4
本章目录 · 1 节
本章导读
本章按教材4.1—4.53保留全部习题组。整除默认除数非零,余数取非负;最大公因数、最小公倍数均取非负规范值,讨论最大公因数的数值大小时应排除两输入同时为0。遇到原题条件不充分时,明确补充条件,而不把错误命题强行证明。
【习题4.1】判断 。
解:前五项依次为假、真、真、假、真。最后两项按本章“除数非零”的定义均不在定义范围内。若另行采用允许零除数的扩展定义 ,则 为假、 为真;两种约定不能混用。
【习题4.2】求24的全部因子。
解:正因子为1、2、3、4、6、8、12、24,若“全部”包括整数因子,还包括它们各自的负数,共16个;0不是因子。
【习题4.3】分别对35除以4、5除以8、12除以3、 除以3、 除以7、 除以 作带余除法。
解:;;;;;。最后一项仍要求 ,不能沿用某些编程语言的负余数结果。
【习题4.4】正整数 下判断并证明或反驳:(1);(2);(3);(4) 或 。
解:(1)假,。(2)真,若 ,则 。(3)真,。(4)假,;若补充 为素数,则成立。
【习题4.5】分解126、256、1092、6325、。
解:依次为 ,,,,以及 。阶乘中素数 的指数用 计算。
【习题4.6】判断113、221、527、 是素数还是合数。
解:113为素数,试除不超过其平方根的2、3、5、7均失败;、 为合数; 为素数,试除不超过90的全部素数均无因子。指数13为素数本身不足以证明最后一项,仍须素性检验。
【习题4.7】设计筛出正整数 以内全部素数的算法。
解:若 返回空表。建立0至 的布尔表,把0、1设为非素;从 递增到 ,若 尚未被划去,就把 全部划去。最后输出所有未划去的2至 的下标。每个合数有不超过平方根的素因子,故不会遗漏;从 开始不会误划素数。
【习题4.8】对任意整数 证明:(1);(2) 为整数。
证明:(1)三个连续整数中有偶数且有3的倍数,因2、3互素,乘积被6整除。(2)通分为 。模3时 ,分子同余于 ;模5时 ,同余于 ,所以分子被互素的3、5共同整除,因而被15整除。结论包括负整数和0。
【习题4.9】整数 时,证明 不是整数。
证明:取 ,令 ,其中2的最高指数恰为 。在所有 中,只有 时为奇数,其余都为偶数,所以通分后的分子为奇数,分母 为偶数;它不可能等于整数。这里利用了区间1至 中只有一个数具有最高的2幂因子。
【习题4.10】(1)素数从小到大为 ,证明 ;(2)证明 ,。
证明:(1) 成立。 的任何素因子都不在前 个素数中,故 ,完成归纳。(2)令 ,则 ,取两次以2为底的对数,得 。
【习题4.11】整数系数多项式 若有非零整数根 ,证明 。
证明:移项得 ,括号内为整数,所以整除。非零条件避免把0当作本章的除数。
【习题4.12】求以下方程全部整数根:(1);(2);(3);(4)。
解:(1)判别式为 ,无实根,当然无整数根。(2)分解为 ,根为 。(3)非零整数根只能为 ,逐个代入均不为0,且0也非根,所以无整数根。(4)分解为 ,最后二次因子判别式为 ,所以整数根恰为0、。
【习题4.13】用素因子分解求175与140、72与108、315与2200的最大公因数和最小公倍数。
解:依次为 、、。分解分别为 ;;。公因数取最小指数,公倍数取最大指数。
【习题4.14】求 的全部正整数有序对。
解:写 ,则 。全部为 ,既不能漏掉交换后的有序对,也不能把公因子仍含2的配对纳入。
【习题4.15】素数 下,证明 时 , 时 。
证明: 的正因子只有1与 。前一种情形 是共同因子,后一种情形它不是共同因子,所以只剩1。
【习题4.16】原题要求对任意整数 证明 。
解:原命题缺少定义域条件。若两个线性组合不全为0,则任意共同因子 均整除两组合,因此整除其正最大公因数,便得到所需不等式。若 ,右侧成为本章未定义的 ;即使扩展约定它为0,也会对 得到错误的 。因此应补充“两线性组合不全为0”,不能把无条件命题强行证明。
【习题4.17】用辗转相除求85与125、231与72、45与36、154与64的最大公因数。
解:,得5;,得3;,得9;,得2。
【习题4.18】判断24与35、63与91、450与539、1024与729是否互素;互素时给出贝祖系数。
解:24与35互素,;63与91不互素,最大公因数为7;450与539互素,;1024与729互素,。代回等式可直接检验系数。
【习题4.19】,求:(1);(2);(3)。
解:(1)公因子整除差2,又因两数均奇,故为1。(2)提出2后连续整数互素,得2。(3),所以 奇时为 ,偶时为 。结果始终取正,不因 为负而改变。
【习题4.20】 不全为0,,证明 当且仅当存在互素整数 使 。
证明:把 除以最大公因数,若商仍有大于1的共同因子,就产生更大的公因数,矛盾。反向由 ;亦可用 得 ,再结合 为共同因子证明。
【习题4.21】正整数 下证明 。
证明:逐个素因子比较指数,右侧指数为 ,与左侧相同,故由素因子分解唯一性得到等式。
【习题4.22】 且 互素,证明 。
证明:取 ,乘 得 ,左侧每项都被 整除,因而右侧也被整除。
【习题4.23】 互素:(1)证明 ;(2)对 ,证明 当且仅当 ,并证明这种正因子分解唯一。
证明:互素使 的素因子集合互不相交。共同因子的每个素数只能来自其中一方,所以在(1)中指数可分别分配后相乘;(2)中把 的每个素因子及其全部指数分给含它的唯一一方,就给出存在性及唯一性。可取 。反向由两个整除式相乘即得 。
【习题4.24】证明 当且仅当 且 。
证明:右推左显然。反向,模11的平方剩余为0、1、3、4、5、9。若 ,可乘 ,得到 ,不在平方剩余表中,矛盾。因此 ,再得 ,素数性质推出 。
【习题4.25】判断 、、、。
解:依次为假、假、真、真。四个差值为512、368、、352,其中前两个分别不能被18、7整除,后两个可被相应模数整除。
【习题4.26】求大于1的全部模数 ,使:(1);(2);(3);(4);(5)同时 (均模 )。
解:把模数看成差值的正因子。(1)3、7、21;(2)11;(3)2、4、7、14、28;(4),故7、67、469;(5)模数须同时整除6与9,故只有3。
【习题4.27】写出 全部元素及其加法、乘法表。
解:全部元素为 ,每一类 ;表中按行、列代表元分别计算和、积再取模7。
【习题4.28】写出 全部元素及其加法、乘法表。
解:全部元素为 ,每一类 。与模素数的情形相比,非零类之积可能为零,例如 ,不能随便消去非零类。
【习题4.29】用教材日期公式求1941年12月7日的星期。
解:,代入 ,所以为星期日。
【习题4.30】验证 月1日与计算年3月1日的星期差为 ,推出较简公式。
解:把教材表中 的累计偏移 分别取模7,与该取整式逐项相同,因此覆盖全部12个月。代入3月1日公式,并加 ,得到
其中 。1、2月必须归入上一计算年,不能直接用原公历年的世纪数与年内数。
【习题4.31】证明模 同余关系自反、对称、传递。
证明:;若 则整除其负数 ;若整除 则整除其和 。这分别给出三种性质,模数保持为同一个正整数。
【习题4.32】若 ,证明 、。
证明:加减法的差为 ;乘法的差为 。它们都是 的整数倍。
【习题4.33】证明:(1)正整数 时模 同余推出模 同余;(2) 当且仅当 ,;(3) 时模 同余可消去共同因子 。
证明:(1)用整除传递性。(2)差式 与 可相互推出,因为 。(3)正向乘 显然;反向用贝祖系数 ,乘 后可知整个右侧均被 整除,所以 。
【习题4.34】判断五个命题:(1) 推出 ;(2) 推出平方同余;(3) 推出 ;(4)模 同余推出分别模 同余;(5)分别模 同余推出模 同余。
解:(1)假,,平方同余,但1既不同余于3也不同余于 。(2)真,乘法保持同余。(3)假,,平方相等但两数模3不同余。(4)真,模数整除规则。(5)一般假,;若补充 互素,则可由两个互素因子共同整除差值而成立。
【习题4.35】求全部解:(1);(2);(3);(4);(5)。
解:(1),即全部奇数。(2)无解, 不整除3。(3)。(4)无解,4不整除2。(5),即全部奇数。列出模原模数的全部解类,不能只保留约化模数下的一个代表。
【习题4.36】对 ,验证 是 的模逆。
解:乘积依次为15、56、121、66,分别等于 ,故全部成立。
【习题4.37】求存在的模逆:(1)2模3;(2)8模12;(3)18模7;(4)12模21;(5)5模9;(6) 模9。
解:依次为2、不存在、2、不存在、2、8。不存在的两项最大公因数分别为4和3,其余代表均可将乘积检验为模数的整数倍加1。
【习题4.38】求整系数方程全部整数解:(1);(2)。
解:(1)模2得 为偶数,写 ,则 ,,这已穷尽全部解。(2)左侧恒被3整除,右侧不被3整除,所以无解。
【习题4.39】、,证明 恰有 个模 解类。
证明:除以 得到系数与模数互素的方程,在模 下唯一解为 。原模数下的解为 ,;两项若模 相同,则 ,在该范围只能相等。任意整数解模 都属于原唯一解类,因此上述列表也没有遗漏。
【习题4.40】,证明 。
证明:写 ,原式等价于 。因 ,可消去 ,得 。模数缩小这一步不可省略。
【习题4.41】素数 下, 推出 或 。
证明:,素数整除乘积必整除某因子,故结论成立。 时两种代表本来就在同一个剩余类中。
【习题4.42】费马数 ,证明不同 互素。
证明:恒等式 可用平方差递推证明。若 ,共同正因子同时整除 和 ,故整除2;费马数均为奇数,所以共同因子只能为1。互素并不表示每个费马数都是素数。
【习题4.43】证明存在无穷多个 满足 。
证明:对每个素数 ,; 为偶数,与它互素的数至多为其中一半,所以 。这样的素数有无穷多个,取 即得。
【习题4.44】正整数 互素,证明 。
证明:两数的素因子集合不交,分别使用欧拉函数乘积式并相乘,就得到 的乘积式。若有一数为1,,结论同样成立。
【习题4.45】用费马小定理计算 。
解:指数分别模4、6、10约化为1、0、3,得到2、1、。应用前先检查底数与相应素数互素。
【习题4.46】正整数 互素,证明 。
证明:当 ,模 时第一项为0,第二项由欧拉定理为1;模 时相反,仍为1。差值同时被互素的 整除,所以被乘积整除。若有一数为1,模数约化到另一个数,结论可直接检验。
【习题4.47】 为整系数多项式, 为素数,证明 。
证明:对整数 ,费马小定理给出 ,多项式保持同余,故 ;再对整数 使用费马小定理,得 ,从而两端同余。若把命题理解为多项式系数模 的恒等式,也可由中间二项式系数均被 整除及 证明。
【习题4.48】,证明 是 上的双射,当且仅当 互素。
证明:互素时,若输出相同,消去 得输入同余;规范输入范围内只能相等,所以单射,有限同势集合间即为双射。反向若 ,不同输入0与 的输出相同,因为 为 的倍数,所以不单射。存在逆时,解密为 。
【习题4.49】给出五组线性同余参数产生的状态序列及周期:(1);(2);(3);(4);(5)。
解:以下先列种子 ,其后按递推产生新状态。(1),周期4。(2),周期9。(3)先有非循环前段1,然后循环 ,最终周期4,不能把前段1计入循环长度。(4),周期8。(5),周期16。若需 ,分别把产生的状态除以对应模数即可。
【习题4.50】用0至25表示A至Z,将XINGDONGZAIZIYE分别用 (模26)加密,密文仍用字母表示。
解:三种密文依次为ALQJGRQJCDLCLBH、FENQVUNQTAETEMC、JMLCNQLCTYMTMOS。所有负值与超过25的值均按模26回到规范范围。
【习题4.51】用每段三个字母的维吉尼亚密码加密同一明文,循环密钥为3、、7。
解:依位置循环加上相应密钥,得AGUJBVQEGDGGLWL。负的第二位密钥表示向前移2位,不能错误地把它取为正2。
【习题4.52】写出4.50三种算法的解密,并恢复原文。
解:三种解密为 、、,因为 。分别作用于对应密文,均恢复XINGDONGZAIZIYE;第二、三项不能把乘法逆误用成普通除法。
【习题4.53】RSA取 ,A至Z编码为00至25,每字符一块:(1)加密STOP;(2)解密32、14、32。
解:,所以可取 。STOP编码为18、19、14、15,分别取7次幂模35,密文为32、19、14、15。对32、14、32分别取7次幂模35,恢复18、14、18,对应SOS。尽管此例加密、解密指数恰相同,也不能据此把RSA的一般公私钥当成相同。
