Math 312 Worksheet - University Of British Columbia -2016 Page 3
ADVERTISEMENT
1
2
3
4
5
6
7
8Math 312, Midterm
3
PROBLEM 2 (10 points)
(a) (2pts) State the definition of the inverse of an integer a modulo
m, where m is a positive integer.
Answer: Any integer x satisfying the congruence ax
1 (mod m)
is called an inverse of a modulo m.
1
(b) (8pts) Compute 13
(mod 55) using the Euclidean algorithm
and back substitution.
Answer: Computing an inverse of 13 modulo 55 amounts to find
the x-coordinate of a solution (x, y) of the equation 13x + 55y = 1. We
first use Euclidean algorithm to compute (13, 55). Indeed,
55 = 13 4 + 3,
13 = 3 4 + 1,
3 = 1 3 + 0
giving (55, 13) = (13, 3) = (3, 1) = (1, 0) = 1. We now apply back
substitution
1 = 13 3 4 = 13 (55 13 4) 4 = 13 55 4+13 16 = 13 17+55 ( 4)
to conclude that (17, 4) is a solution of to the equation above. Thus
x = 17 (mod 55) is the inverse of 13 modulo 55.
ADVERTISEMENT
0 votes
Related Articles
Related forms
Related Categories
Parent category: Education