Appendix: Solutions to Problems
Lynn Batten · Public Key Cryptography · 2013
Full solutions for the odd-numbered questions are provided here.A full solution set is available from the publisher. Solutions to2.1.21.(a) n always divides aa = 0. (b) If n|a, then n|(a -0) and we get the result.Conversely, if n|(a -0), then n|a.(c) This follows from n|(ab) precisely when n|(ba).(d) If n|(ab) and n|(bc), then n|((ab) + (bc)), so n|(ac).3. We test each in turn, as in Example 2.3.Only 1, 3, 7, and 9 have inverses which are, respectively, 1, 7, 3, and 9. Checking each of the 11 possible values, we see that there is only one: 9. 5.The Maple command gcd(65537, 3511); produces output 1. Solutions to 2.2.21.In this case, b divides into a and the gcd is b.You can still write b = a -(q 1 -1)b.3. 3127 = 2563 * 1 + 564.2563 = 564 * 4 + 307.564 = 307 * 1 + 257.307 = 257 * 1 + 50.257 = 50 * 5 + 7.50 = 7 * 7 + 1.Thus, 1 is the last non zero remainder and the gcd and so 2563 does have an inverse modulo 3127.To find the inverse, we backtrack the equations to get from Maple igcdex(2563, 3127,"x," "y"); x; y; producing 1, 438, -359 so 1 = 2563 * 438 -3127 * 359.Now taking this equation modulo 3127, the inverse of 2563 is 438. 5. (a) Any solution x common to the equations must satisfy both the equationsx -2 = 6k for some integer k and x -3 = 4m for some integer m.The first equation implies that x must be even.If this holds, then the second equation implies that 3 is even, which is false.So there is no solution.