## P1

Use the Euclidean algorithm to find the GCD of
2017 and 1995. Show each step.

What does this tell you about the possibility of finding
a number x so that 1995*x mod 2017 = 99?

## P2

Compute the following entirely by hand, showing all your work:
\[
(35 \cdot (42 + 19)) \cdot (18 + 46)^2 \mod 11
\]
## P3

Trace through the Extended Euclidean algorithm (as presented in
the notes) on input 17 and 12. I strongly recommend you make a
table like this:

a b | q r g0 s0 t0 g s t
-------------------------------------------------------------------------
XGCD( 21 8 ) | 2 5 1 2 -3 1 -3 8
XGCD( 8 5 ) | 1 3 1 -1 2 1 2 -3
XGCD( 5 3 ) | 1 2 1 1 -1 1 -1 2
XGCD( 3 2 ) | 1 1 1 0 1 1 1 -1
XGCD( 2 1 ) | 1 0 1 1 0 1 0 1
XGCD( 1 0 ) | 1 1 0

## P4

Show how to use the above results to find the multiplicitive
inverse of 12 in $Z_{17}$.