同题集4的解 到期：星期一，2月28目下午9点 间题1迁明所有以下陈述除，了有二个为假：对于郑些，提供反例。假设■>1。当证 明每个陈述的时候，您可以假设所有它的前面部分， (aa■a(modn 解：每个数字可整除零，如此nKa-a意味a=a(mod: (b)■b(mod n)道话b■a(modn) 解：陈述a口b(mod)蕴海叫ab,意味着存在整数k以至于止a-b。因此，n(k户 ba,因此nb-a.这意味着b■amdn以。 (en■b(mod且b■c(modn道涵a■e(modn) 解：二个假定蕴诵nab)和叫b-c.因此，n除以线性组合ab+b-ca-c.这 意味着na-c: (da■b(modn功unhana+c■b+c(mod) 解：第一个声明崔测n|(仁b重写右边给出可(a+c十h+,这意味a+e■b+e(mod n). (e)a■b (mod n)盖涵c■bo(mod n) 解：第一个声明鹤通川(ab)。因此。n也整释c信bF女bc。所以。x■b比(mod n). 0e■(mdn)蕴话a-b(mdn提供有C丰0(m0dn)】 解：这是为假的.。例如，6·2=8·2(mod4.但是6丰8(m0d4)】 (g》a■b(mod n)和c■d(odn)道话a+e■b+d(modn) 解：假定，与部分©)一起，给： a+c≡b+c(modn】 b+c三b+d(modn 现在部分(c题涵a+e■b+d(modn): ha■b(modn和e■d(modn)道ac■bd(modn) 解：假定，与部分e一起，给： ac≡bc (mod n) bc≡bd (modn)】 FDF文件使用“pdfFactory Pro”试用版本创建fineprint,n
问题集 4 的解 到期 ： 星期一， 2 月 28 日下午 9 点 问题 1 证明所有以下陈述除，了有二个为假； 对于那些，提供反例。 假设 n > 1。 当证 明每个陈述的时候，您可以假设所有它的前面部分。 (a) a≡ a (mod n) 解： 每个数字可整除零，如此 n |(a − a)，意味 a ≡ a (mod n)。 (b) ≡ b (mod n) 蕴涵 b ≡ a (mod n) 解：陈述 a≡ b (mod n) 蕴涵 n| (a− b)，意味着存在整数 k，以至于 nk =a − b。因此，n (−k)= b− a，因此 n |(b− a)。 这意味着 b ≡ a (mod n)。 (c)a ≡ b (mod n)且 b ≡ c (mod n)蕴涵 a ≡ c (mod n) 解： 二个假定蕴涵 n |(a− b)和 n| (b− c)。 因此， n 除以线性组合(a− b)+ (b − c)= a− c。 这 意味着 n |(a− c)。 (d) a ≡ b (mod n)yunhan a + c ≡ b + c (mod n) 解： 第一个声明蕴涵 n | (− b)。 重写右边给出 n| (a + c)− (b + c)，这意味 a + c ≡ b + c (mod n)。 (e) a ≡ b (mod n) 蕴涵 ac ≡ bc(mod n) 解： 第一个声明蕴涵 n| (a−b)。 因此， n 也整除 c (a−b)= ac−bc。 所以， ac ≡ bc (mod n)。 | (f) ac ≡ (mod n) 蕴涵 a ≡ b (mod n)提供有 。 解： 这是为假的。 例如， 6·2 ≡ 8 · 2 (mod 4)，但是 。 (g) a≡ b (mod n)和 c ≡ d (mod n)蕴涵 a + c ≡ b + d (mod n) 解： 假定，与部分(e)一起，给： 现在部分 (c)蕴涵 a + c ≡ b + d (mod n)。 (h) a ≡ b (mod n)和 c ≡ d (mod n)蕴涵 ac ≡ bd (mod n) 解： 假定，与部分(e)一起，给： PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
现在部分(c)面涵ae■be(modn. ia■b(modn道酒a■(modn.对所有k的≥0. 解：我门使用归纳法。假设a■b(o).令Pk)是■b的命题. 基例，P0为真，因为a=b=1和由部分a得，1■1(mdm为真. 归销步：对于k≥0，我们假设P(k)来正明Pk+1).因此，假设广=b(mcd。结 合这假设和事实a=b(mdn,使用部分(g: 我们得到■b(modn. 由归钠法得，Pk)对所有k≥0成立。 U)a■b(modn道通k=k(mcdn.对于所有k的≥0. 新这是铅议的。例知，0一3m则》自是2°≠2 (mod 3) (k(a REMn■a(mod n) 解：由rm的定义。amn=aq对于某个整数q米说。因此我们可以挂理如下： (a rem n)=a-gn (mod n) 三a(modn) from(d)and gn≡0(modn) 问题2正明存在一个整数k,以便 .1 (mod n) 提供c域k)=I。假设n>1. 解：如果dk,n)l,那里然后存在整数x和y使得kx+n■l。所以，yn■l-k 意味r1-kx)和因此kx■1(modn).令k是x 问愿3回顾对RSA的分析的也许帮册您解决以下问题。您可以假设在复习练习中证明的 结果。 )令n是一个负整数。证明，n和n有同一个最后数字。例如： 2=32793=3077056599 解：RSA的正确性依章以下事宾：如果P和q是不同的质数，那么 ml+kp-1(q-1)三m (mod pq) 对于所有m和k。设置k=1,p=5和q=2证明断言。 )假设内，“，N是不同的质数。证明那 PF文件使用"pdfFactory Pro”试用版本创建w.fineprint,cn
现在部分 (c) 蕴涵 ac ≡ bc (mod n)。 (i)a ≡ b (mod n)蕴涵 a k ≡ bk (mod n)，对所有 k 的≥ 0。 解： 我们使用归纳法。 假设 a≡ b (mod n)。 令 P (k)是 a k≡ bk的命题。 基例：P (0)为真，因为 a 0 = b0 =1 和由部分(a)得，1 ≡ 1 (mod n)为真。 归纳步： 对于 k ≥ 0，我们假设 P (k)来证明 P (k + 1)。 因此，假设 a k≡ bk (mod n)。 结 合这假设和事实 a≡ b (mod n)，使用部分(g)。 我们得到 a k+1 ≡ bk+1 (mod n)。 由归纳法得， P (k)对所有 k ≥ 0 成立。 (j) a≡ b (mod n)蕴涵 k a≡k b (mod n)，对于所有 k 的≥ 0。 解： 这是错误的。 例如， 0 ≡ 3 (mod 3)，但是 。 (k) (a REM n) ≡ a (mod n) 解： 由 rem 的定义，a rem n =a –qn，对于某个整数 q 来说。 因此我们可以推理如下： 问题 2 证明存在一个整数 k-1，以便 提供 gcd(k,n) = 1。假设 n > 1。 解： 如果 gcd (k， n) =1，那里然后存在整数 x 和 y 使得 kx + yn =1。 所以， yn =1 − kx， 意味 n| (1 − kx)和因此 kx ≡ 1 (mod n)。 令 k −1是 x。 问题 3 回顾对 RSA 的分析的也许帮助您解决以下问题。 您可以假设在复习练习中证明的 结果。 (a) 令 n 是一个非负整数。 证明， n 和 n 5有同一个最后数字。 例如： 2 5 = 32 795 = 3077056399 解： RSA 的正确性依靠以下事实： 如果 p 和 q 是不同的质数，那么 对于所有 m 和 k，设置 k =1， p =5 和 q =2 证明断言。 (b)假设 p1，…， pk是不同的质数。 证明那 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
m+m-1m-l--≡m(mod pip2…p%) 对于所有的m和所有k≥1. 解：如果m是质数乃的倍数，那么 m+-1-y-)三m(mod) () 成立，因为双方都和0同余。如果m不是的倍数。那么同余也成立，因为 7m+n-1n-1小--1)=m·(m-1-1W-1小-g-1/W例-)(mod乃) 三m-1-1-1-m-1/-》）(m0dp) =m(od】 第二步使用Fea定理。现在同余)意味那！ p|m1+m-1-l)-p-)-m 因此，乃出现于右边的质数分解中。因为这个对每个质数：这里1名j≤k都有效： 所有的质数都出现在质数分解中： m1+m-1m-1)-p%-1）-m 因此： p1p2…p|m1+m-1段-1p跳-)-m 重写这个同余给出： m1+-1段-1-%-1)=m (modp1p2…P% 问题4假设p是质数。 (a)整数k是自反的，如果k·k■1(modp.寻找所有mdp的自反转的整数 解：同余成立，如果当且仅当当与k-1,其等于刊k+)k-):这是成立的，当且仅 当减者pk+1,或者pk-1。因此.k■1(modp小， (b)Wilson's定理说(p-11■-1(mcdp.英国数学家Edward Waring说这个陈述大颗是 极端难证明，因为没人基至发明了足够的符号来处理质数。（高斯证明了它，在站立的时候，） F文件使用"pdfFactory Pro”试用版本创建w.finsprint,n
对于所有的 m 和所有 k≥ 1。 解： 如果 m 是质数 pj的倍数，那么 成立，因为双方都和 0 同余。 如果 m 不是 pj的倍数，那么同余也成立，因为 第二步使用 Fermat 定理。 现在同余(*)意味那： 因此， pj出现于右边的质数分解中。 因为这个对每个质数 pj，这里 1 ≤ j≤ k，都有效， 所有的质数都出现在质数分解中： 因此： 重写这个同余给出： 问题 4 假设 p 是质数。 (a)整数 k 是自反转的，如果 k·k≡ 1 (mod p)。 寻找所有 mod p 的自反转的整数 解：同余成立，如果当且仅当当与 p|k2 − 1，其等于 p| (k+ 1) (k−1)。这是成立的，当且仅 当或者 p | k+1，或者 p | k-1。 因此， k≡ ±1 (mod p)。 (b) Wilson’s 定理说那(p−1)! ≡ −1 (mod p)。 英国数学家 Edward Waring 说这个陈述大概是 极端难证明，因为没人甚至发明了足够的符号来处理质数。 (高斯证明了它，在站立的时候。) PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
现在轮到您站起来了，如果您喜政，并且设法成对去掉(P1川的项。 解：如果p-2,那么定理成立，因为11■-1m0d2)。如果p>2,然后p1和1是在在 乘积【一P-中的不同的项，和这些是仅自反转的。结果是，我们能用它的乘积反转成对 每个剩余的项，因为数字和它的反面的乘积是和1同余的，所有这些剩余的项被去掉了。所 以，我们有： (p-1)！≡1·(p-1) (mod p) =-1 (mod p) FDF文件使用“pdfFactory Pro”试用版本创建fineprint.cn
现在轮到您站起来了，如果您喜欢，并且设法成对去掉(p-1)!的项。 解： 如果 p =2，那么定理成立，因为 1! ≡ −1 (mod 2)。 如果 p> 2，然后 p−1 和 1 是在在 乘积 1 ····(p−1)中的不同的项，和这些是仅自反转的。结果是，我们能用它的乘积反转成对 每个剩余的项，因为数字和它的反面的乘积是和 1 同余的，所有这些剩余的项被去掉了。所 以，我们有： PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn