- #1
Benny
- 584
- 0
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
[tex]3 \times 31 \equiv 1\left( {\bmod 23} \right)[/tex]
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.
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
[tex]3 \times 31 \equiv 1\left( {\bmod 23} \right)[/tex]
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.