## 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]
^{-1}_{18} (i.e., the multiplicative
inverse of 7 in **Z**/18**Z**). Show how you obtain your answer.
- Since [7]
_{18}[13]_{18} = [91]_{18}
= [1]_{18}, we see that [7]^{-1}_{18}=[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]
^{-1}_{18} does not exist
(i.e., why 8 has no multiplicative
inverse in **Z**/18**Z**).
- 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**/m**Z**,
then bx == c mod m always has a solution, and it is unique.
If b does not have a multiplicative inverse in
**Z**/m**Z**, 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.