Thread: Euclidean Algorithm

Use the Euclidean Algorithm to find 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)

You have found that in . What is the definition of a multiplicative inverse?

Originally Posted by farmeruser1

Use the Euclidean Algorithm to find 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.