## Math 310: Problem set 2

Instructions: This problem set is due Thursday, September 7, 2006. Your goal is not only to give correct answers but to communicate your ideas well. Make sure you use good English.
1. Read Chapter 2ABCD of the text.
2. Find [7]-118 (i.e., the multiplicative inverse of 7 in Z/18Z). Show how you obtain your answer.
• Since [7]18[13]18 = [91]18 = [1]18, we see that [7]-118=[13]18. (We saw in class that multiplicative inverses are unique, so [13]18 is the only solution to [7]18[x]18 = [1]18.)
3. Explain why [8]-118 does not exist (i.e., why 8 has no multiplicative inverse in Z/18Z).
• If it did exist, then there would be a solution to [8]18[x]18=[1]18. This is the same thing as there being a solution to 8x = 1 + q18, or 8x - 18q = 1. But 8x - 18q is always even while 1 is odd, so there can be no integers x and q such that 8x - 18q equals 1.
4. Find the least nonnegative value of x such that 7x == 11 mod 18. Show how you obtain your answer.
• Just multiply through by the multiplicative inverse of 7; i.e., if 7x == 11 mod 18, then x = 1*x == 13*7x == 13*11 == 17 mod 18.
5. Prove that 8x == 11 mod 18 has no solution.
• If x is a solution, then 8x = 11 + q18 for some integer q, hence 8x - 18q (which is even) equals 11 (which is odd). This is not possible, so there is no solution.
6. Find all values of x from 0 to 17 for 8x == 2 mod 18. Show how you know you found them all.
• There are two solutions, x = 7 and x = 16. To show they are solutions, just plug them in and check. By plugging in the other values of x from 0 to 17, we can check that there are no other solutions.
Moral of this assignment: Consider bx == c mod m. If b has a multiplicative inverse in Z/mZ, then bx == c mod m always has a solution, and it is unique. If b does not have a multiplicative inverse in Z/mZ, then, depending on c, bx == c mod m might have a solution, or it might not, and when it does, there can be more than one solution.