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 $\displaystyle p$ for which $\displaystyle 4p\equiv1\mod9$; in other words the value(s) of $\displaystyle p$ for which:$\displaystyle 4p+9q=1$, where $\displaystyle q$ is another integer

You have correctly found, using the Euclidean Algorithm, that$\displaystyle 4\times (-2)+9\times1 = 1$

So you have the solution$\displaystyle p=-2, q=1$

So you have, in fact, found an inverse of $\displaystyle 4 \mod 9$, and that is $\displaystyle -2$. Check it out:$\displaystyle 4\times(-2) = -8 \equiv 1 \mod9$

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

$\displaystyle -2 + 9n \equiv -2 \mod 9$ for any integer $\displaystyle n$

Of course, all you need to add is $\displaystyle 9$ itself, and get $\displaystyle -2+9=7$. So $\displaystyle 7$ is also an inverse of $\displaystyle 4$. Check this one out:

$\displaystyle 4\times7=28\equiv1 \mod9$

This gives us another solution to the equation

$\displaystyle 4p+9q=1$

and that is

$\displaystyle p=7,q=-3$

There are infinitely many others that you can find in a similar way:$\displaystyle p=16, q=-7;\quad p=-11, q = 5,$...etc.

Does that help to clear things up?

Grandad