Thread: inverse of 4 modulo 9

I have tried to follow the previous posts and I'm still confused.
I can follow the Euclidean algorithm to find gcd and I know that gcd has to equal 1 for there to be an inverse, in other words a and m have to be relatively prime, but could someone lay out the steps? Let a=4 and m=9.

Then 9 = 2(4) + 1
and 4 = 4(1) + 0

so 1 = 9 - 2(4)

Then do you set 4p = 1 (mod 9) ?

I really don't understand how the process (algorithm) continues.

Hello oldguynewstudent

Originally Posted by oldguynewstudent

I have tried to follow the previous posts and I'm still confused.
I can follow the Euclidean algorithm to find gcd and I know that gcd has to equal 1 for there to be an inverse, in other words a and m have to be relatively prime, but could someone lay out the steps? Let a=4 and m=9.

Then 9 = 2(4) + 1
and 4 = 4(1) + 0

so 1 = 9 - 2(4)

Then do you set 4p = 1 (mod 9) ?

I really don't understand how the process (algorithm) continues.

You're correct in what you have so far. Let me summarise:

The problem is to find the value(s) of for which ; in other words the value(s) of for which:

, where is another integer

You have correctly found, using the Euclidean Algorithm, that

So you have the solution

So you have, in fact, found an inverse of , and that is . Check it out:

But perhaps you were looking for an inverse between and . So you simply add enough 's to your solution until you get a value in this range. This works because

for any integer

Of course, all you need to add is itself, and get . So is also an inverse of . Check this one out:

This gives us another solution to the equation

and that is

There are infinitely many others that you can find in a similar way: ...etc.

Does that help to clear things up?

Grandad

Originally Posted by Grandad

Hello oldguynewstudentYou're correct in what you have so far. Let me summarise:

The problem is to find the value(s) of for which ; in other words the value(s) of for which:

, where is another integer

You have correctly found, using the Euclidean Algorithm, that

So you have the solution

So you have, in fact, found an inverse of , and that is . Check it out:

But perhaps you were looking for an inverse between and . So you simply add enough 's to your solution until you get a value in this range. This works because

for any integer

Of course, all you need to add is itself, and get . So is also an inverse of . Check this one out:

This gives us another solution to the equation

and that is

There are infinitely many others that you can find in a similar way: ...etc.

Does that help to clear things up?

Grandad

Wow! How did you make it so simple when my professor filled up 3 blackboards with infinite tangeants. This was immensely helpful!

A little more explicitly than Grandad so nicely put. If is a solution to then any element of is a solution. For let then