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.
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.
- Read Chapter 2ABCD of the text.
- Find -118 (i.e., the multiplicative
inverse of 7 in Z/18Z). Show how you obtain your answer.
- Since 1818 = 18
= 18, we see that -118=18. (We saw in class that multiplicative
inverses are unique, so 18 is the only solution to
18[x]18 = 18.)
- Explain why -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
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.