# Euclidean Algorithm

• December 4th 2011, 06:00 AM
farmeruser1
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)
• December 4th 2011, 06:10 AM
ymar
Re: Euclidean Algorithm
You have found that $11\cdot 17 = 1$ in $\mathbb{Z}_{31}$. What is the definition of a multiplicative inverse?
• December 5th 2011, 05:59 AM
dwsmith
Re: Euclidean Algorithm
Quote:

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.