# Solutions to Problem Set 23

Math 310-01/02

11-8-2017

1. Simplify the following expressions. Your answers should be in the range .

(a) .

(b) .

(c) .

(a)

(b)

(c)

2. If , the multiplicative inverse of x mod n is denoted . It is the number (if there is one) which satisfies the equations

(b) Show that 4 does not have a multiplicative inverse mod 6.

(a) Since , it follows that .

(b) One approach is to try all the numbers in :

Alternatively, you can give a proof by contradiction. Suppose . Multiply both sides by 3:

The last line is a contradiction, and so there is no number x such that .

3. Use modular arithmetic to prove that if , then is not divisible by 5.

If , then , 1, 2, 3, or 4 mod 5. I take cases:

For all x I have . It follows that if , then is not divisible by 5.

4. Give specific values of and with to show that the following statement is false:

"If , then ."

Take , , , and . Then . However, and , and .

Nothing is so exhausting as indecision, and nothing is so futile. - Bertrand Russell

Contact information