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.
- Read Chapter 2ABCD of the text.
- 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.)
- 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.
- 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.
- 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.
- 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.