# Math Help - inverse of 4 modulo 9

1. ## 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.

2. ## Inverses in modular arithmetic

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 $p$ for which $4p\equiv1\mod9$; in other words the value(s) of $p$ for which:
$4p+9q=1$, where $q$ is another integer
You have correctly found, using the Euclidean Algorithm, that
$4\times (-2)+9\times1 = 1$
So you have the solution
$p=-2, q=1$
So you have, in fact, found an inverse of $4 \mod 9$, and that is $-2$. Check it out:
$4\times(-2) = -8 \equiv 1 \mod9$
But perhaps you were looking for an inverse between $0$ and $8$. So you simply add enough $9$'s to your solution until you get a value in this range. This works because
$-2 + 9n \equiv -2 \mod 9$ for any integer $n$
Of course, all you need to add is $9$ itself, and get $-2+9=7$. So $7$ is also an inverse of $4$. Check this one out:
$4\times7=28\equiv1 \mod9$
This gives us another solution to the equation
$4p+9q=1$
and that is
$p=7,q=-3$
There are infinitely many others that you can find in a similar way: $p=16, q=-7;\quad p=-11, q = 5,$...etc.

Does that help to clear things up?

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

The problem is to find the value(s) of $p$ for which $4p\equiv1\mod9$; in other words the value(s) of $p$ for which:
$4p+9q=1$, where $q$ is another integer
You have correctly found, using the Euclidean Algorithm, that
$4\times (-2)+9\times1 = 1$
So you have the solution
$p=-2, q=1$
So you have, in fact, found an inverse of $4 \mod 9$, and that is $-2$. Check it out:
$4\times(-2) = -8 \equiv 1 \mod9$
But perhaps you were looking for an inverse between $0$ and $8$. So you simply add enough $9$'s to your solution until you get a value in this range. This works because
$-2 + 9n \equiv -2 \mod 9$ for any integer $n$
Of course, all you need to add is $9$ itself, and get $-2+9=7$. So $7$ is also an inverse of $4$. Check this one out:
$4\times7=28\equiv1 \mod9$
This gives us another solution to the equation
$4p+9q=1$
and that is
$p=7,q=-3$
There are infinitely many others that you can find in a similar way: $p=16, q=-7;\quad p=-11, q = 5,$...etc.

Does that help to clear things up?

4. A little more explicitly than Grandad so nicely put. If $x_0$ is a solution to $ax\equiv 1\text{ mod }n$ then any element of $X=\left\{x\in\mathbb{Z}:x=x_0+nz\quad z\in\mathbb{Z}\right\}$ is a solution. For let $\xi\in X$ then $a\xi=a(x_0+nz)=ax_0+anz\equiv ax+0\equiv1+0=1\text{ mod }n$