Mathematics for Computer Science

8.9. What has SAT got to do with it? 221

prime,p. Find a solution to the congruences

ym 1 xCb 1 .modp/

ym 2 xCb 2 .modp/

whenm 1 6m 2 .modp/. Express your solution in the formx‹ .modp/and
y ‹ .modp/where the ?’s denote expressions involvingm 1 ,m 2 ,b 1 , andb 2.
You may find it helpful to solve the original equations over the reals first.

Problem 8.13.
LetSkD 1 kC 2 kC:::C.p1/k, wherepis an odd prime andkis a positive
multiple ofp 1. Use Fermat’s theorem to prove thatSk1 .modp/.

Homework Problems

Problem 8.14. (a)Use the Pulverizer to find the inverse of 13 modulo 23 in the
intervalŒ1;23/.

(b)Use Fermat’s theorem to find the inverse of 13 modulo 23 inŒ1;23/.

Problems for Section 8.7

Practice Problems

Problem 8.15. (a)Prove that 2212001 has a multiplicative inverse modulo 175.

(b)What is the value of.175/, whereis Euler’s function?

(c)What is the remainder of 2212001 divided by 175?

Problem 8.16. (a)Use the Pulverizer to find integerss;tsuch that

40sC7tDgcd.40;7/:

Show your work.

(b)Adjust your answer to part (a) to find an inverse modulo 40 of 7 inŒ1;40/.

Class Problems

Problem 8.17.
Supposea;bare relatively prime and greater than 1. In this problem you will prove