- This is part of 01204211-58.
In-class activities
A.1 Implement the Extended-GCD algorithm and use it to find, for each following pair of
and
, the g.c.d. of
and
and a pair of integers
such that
.
(a)
(b)
(c)
(d)
(e)
your student id,
the student id of another student sitting next to you. (Don't forget to write down the values of
and
as well.
A.2 Use the Extended-GCD algorithm to find the modular multiplicative inverse for the divisor in each of the following question and find the result of the modular division. If the inverse does not exist, you can just state the fact and state that the division cannot be found.
(E.g., if the question is to find 4/3 (mod 11), you have to find
and then find
such that
(mod 11).)
(a)
(mod
)
(b)
(mod
)
(c)
(mod
)
(d)
(mod
)
(e)
(mod
)
Homework