Math Is Fun Forum

parthenos

Member

Registered: 2008-08-25

Posts: 9

Abstract Algebra / multiplicative inverse

I need help solving the following problem.

For the following pair of integers a and n, show that a is relatively prime to n and determine the multiplicative inverse of ā in Z/nZ.

a = 69, n = 89

Daniel123

Member

Registered: 2007-05-23

Posts: 663

Re: Abstract Algebra / multiplicative inverse

To show they're relatively prime, can you not just use the Euclidean Algorithm (:)). I have no idea what the second part of the question means though

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Abstract Algebra / multiplicative inverse

Find integers r and s such that

. This can be done using the Euclidean algorithm. Then

; i.e.

is the multiplicative inverse of

in

.

I’ll do a different example to give you an idea how it’s done. Suppose

.

Hence

; i.e. the multiplicative inverse of

in

is

.

Last edited by JaneFairfax (2008-08-26 02:38:10)

parthenos

Member

Registered: 2008-08-25

Posts: 9

Re: Abstract Algebra / multiplicative inverse

Thank you so much...I was able to get to the second to last line but wasn't sure about the very end.