# Math Help - Euclidean Algorithm

1. ## Euclidean Algorithm

Use the Euclidean Algorithm to ﬁnd the multiplicative inverse of 17 in Z31:
So Ive done MOST of the calculations,
a=17 p=31
..... I then get 1=(11)17-(6)31 [note 31=0 in Z31]
so 1=(11)17 Butt 11 in Z31 is -20?
so 11(-20)=-340
-340=1 mod (31) or... is the answer 340= -1 mod (31)

2. ## Re: Euclidean Algorithm

You have found that $11\cdot 17 = 1$ in $\mathbb{Z}_{31}$. What is the definition of a multiplicative inverse?

3. ## Re: Euclidean Algorithm

Originally Posted by farmeruser1
Use the Euclidean Algorithm to ﬁnd the multiplicative inverse of 17 in Z31:
So Ive done MOST of the calculations,
a=17 p=31
..... I then get 1=(11)17-(6)31 [note 31=0 in Z31]
so 1=(11)17 Butt 11 in Z31 is -20?
so 11(-20)=-340
-340=1 mod (31) or... is the answer 340= -1 mod (31)
As a note, this should be in Number Theory.