Chapter 8 Number Theory300
(b)Assumen > 1. Explain how to use the numbersx;yto find the inverse ofm
modulonwhen there is an inverse.
Problem 8.43.
What is the multiplicative inverse (mod 7) of 2? Reminder: by definition, your
answer must be an integer between 0 and 6.
Problem 8.44. (a)Find integer coefficients,x,y, such that25xC32yDgcd.25;32/.
(b)What is the inverse (mod 25) of 32?Problem 8.45. (a)Use the Pulverizer to find integerss;tsuch that
40sC7tDgcd.40;7/:(b)Adjust your answer to part (a) to find an inverse modulo 40 of 7 inŒ1;40/.Class Problems
Problem 8.46.
Two nonparallel lines in the real plane intersect at a point. Algebraically, this means
that the equations
yDm 1 xCb 1
yDm 2 xCb 2have a unique solution.x;y/, providedm 1 ¤m 2. This statement would be false if
we restrictedxandyto the integers, since the two lines could cross at a noninteger
point:
However, an analogous statement holds if we work over the integersmodulo a
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.