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}$.