# Thread: 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 $\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?

Hello oldguynewstudentYou'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?

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

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

,
,

,

,

,

,

,

,

,

,

,

,

,

# 4 mod 9

Click on a term to search for related topics.