Finding Multiplicative Inverse of 23 in Z_31

[Benny]

There's something that's been bothering me with the division algorithm for a while.

a = dq + r where r < |d| and a,d,q,r are integers. This can be used to find the multiplicative inverse of an integer in Z_m where m is an integer if certain conditions are satisfied. For example if I had two integers 23 and 31, they are relatively prime. So I can find the multiplicative inverse of 31 in Z_23 as follows.

31 = 1 * 23 + 8
.
.
.
3*31 - 1 = 4 * 23
$$3 \times 31 \equiv 1\left( {\bmod 23} \right)$$

So the multiplicative inverse of 31 in Z_23 is 3. How would I go about doing the opposite? That is, finding the multiplicative inverse of 23 in Z_31? With the 'reverse' problem, having done a few questions of this type, I've noticed a pattern where 'multiples' of 31 and 23 in the final equation 3 * 31 - 1 = 4*23 are taken in some combination(can't really recall it right now) and this gives the answer to the 'reverse' problem. I'm not sure if that is just a coincidence or if it is actually meant to work so can someone help me find the multiplicative inverse of 23 in Z_31? The two integers are relatively prime so it should exist. Any help appreciated.

 

[Hurkyl]

What you really want to use are GCDs.

 

[Benny]

What you've suggested seems to be what I should be looking at. I come to this conclusion because I have also used the division algorithm to find GCDs. However I still can't make the connection with how to find the multiplicative inverse of 23 in Z_31.

Some of the steps I omitted in my original post are as follows:

31 = 1*23 + 8
23 = 2*8 + 7
8 = 1*7 + 1
7= 7*1 + 0

I'm not sure what I can do here. I'd prefer to be able to use the division algorithm to find the multiplicative inverse if that's possible. Finding GCDs for pairs of 'small' numbers by factorising them is fairly easily but for pairs of large numbers this becomes very difficult. I know that by some theorem, if d is the gcd of two integers a and b then $$d = \alpha a + \beta b$$ where alpha, beta, a, b and d are integers. But that seems to simply reduce to using the equation 3*31 - 1 = 4 * 23, which is what I had in the first place. I've thought about this but I can't come to a logical conclusion. Could you please provide me with further assistance?

 

[Hurkyl]

Some of the steps I omitted in my original post are as follows:

Those are essentially the steps of the (extended) Euclidean algorithm for computing GCDs -- it's very cheap to do.

Notice that you can reorganize as

8 = 31 - 23
7 = 23 - 2*8
1 = 8 - 7

and work backwards to get an expression for 1 as a linear combination of 23 and 31. (You might be able to do the bookkeeping in a slightly more clever way)

 

[Benny]

Hmm from my original post I have 3*31 - 1 = 4*23.

What I want is the 'roles' of 31 and 23 switched around. 31 is 23 + 8 and 23 is 31 - 8 so 3*(23+8) - 1 = 4*(31-8) => 3*23 - 1 = 4*31 - 7*8 = 4*31 - 7*(31-23) = > -4 * 23 - 1 = -3*31.

In other words:

$$- 4 \times 23 \equiv 1\left( {\bmod 31} \right)$$

So the multiplicative inverse of 23 in Z_31 is $$- 4 \equiv 27\left( {\bmod 31} \right)$$. Is the reasoning correct?

 

[Hurkyl]

Yes, the multiplicative inverse of 23 is -4, modulo 31.