How Do You Find the Inverse of 5 in Z12?

[Rectifier]

The problem
Consider a ring ##(Z_{12}, \oplus, \otimes)##
Find ##5^{-1}##.

The attempt
I am basically searching for an inverse to ##5^{-1}## (if I am correct then judging from previous examples in my book, 5 wouldn't qualify)

Since rings are about residues (the set ##Z_{12}## includes residues as integer elements from 0 to 11) we are basically searching for an integer ##x## that when multiplied by ##5^{-1}## and for which ## R_{12}(x \cdot 5^{-1}) = 1 ## so if ##x =65## would produce that result sine ##65/5=13## and the residue when dividing by ##12## is ##1##, ##65## is an inverse to ##a## since its residue product is ##1##.

Now, for some reason we are supposed to search for ##gcd(12, 5)## I don't really understand why and why there is 5 there and not ##5^{-1}## (well, I get that ##5^{-1}## is less between 0 and 1, thus it is not included since it is not an integer but why is it 5?). Somehow they know that the integer is going to be 1 so they want to express that integer as a Bezout's identity (Euclides algorithm backwards) and finally get an expression for (something). I have not figured it out yet since I don't know why we don't take ##x## from before into consideration yet.

I hope that this was not too long and not many questions. Please help, I have really been trying to figure this stuff out but got stuck at this.

 

[Mark44]

The problem
Consider a ring ##(Z_{12}, \oplus, \otimes)##
Find ##5^{-1}##.

The attempt
I am basically searching for an inverse to ##5^{-1}##

No, I don't think so. Above, you have "Find 5^-1"
Presumably this means that you want to find a number x in Z₁₂ such that 5x = 1. If you do a multiplication table with a row of all of the possible products with 5, you should find an inverse.

(if I am correct then judging from previous examples in my book, 5 wouldn't qualify)

Since rings are about residues (the set ##Z_{12}## includes residues as integer elements from 0 to 11) we are basically searching for an integer ##x## that when multiplied by ##5^{-1}## and for which ## R_{12}(x \cdot 5^{-1}) = 1 ## so if ##x =65## would produce that result sine ##65/5=13## and the residue when dividing by ##12## is ##1##, ##65## is an inverse to ##a## since its residue product is ##1##.

Now, for some reason we are supposed to search for ##gcd(12, 5)## I don't really understand why and why there is 5 there and not ##5^{-1}## (well, I get that ##5^{-1}## is less between 0 and 1, thus it is not included since it is not an integer but why is it 5?). Somehow they know that the integer is going to be 1 so they want to express that integer as a Bezout's identity (Euclides algorithm backwards) and finally get an expression for (something). I have not figured it out yet since I don't know why we don't take ##x## from before into consideration yet.

I hope that this was not too long and not many questions. Please help, I have really been trying to figure this stuff out but got stuck at this.

 

[Rectifier]

Thank you for your reply but unfortunately it didnt make my life easier.I should have specified that in the question above but I am supposed to solve it using gcd and Euclids identity.

 

[Mark44]

Thank you for your reply but unfortunately it didnt make my life easier.I should have specified that in the question above but I am supposed to solve it using gcd and Euclids identity.

Well, gdc(12, 5) = 1, which means that 12 and 5 are relatively prime. It has been a long time since I studied number theory, so I'm not sure what you need to do with this.

However, there are four numbers in Z₁₂ that are relatively prime to 12: 1, 5, 7, and 11. All of these numbers have inverses in this ring. None of the other numbers (that aren't relatively prime to 12) do.

You have a couple of mistakes in what you have posted, that I believe are making things more difficult for you. First, you are not searching for an inverse for 5^-1 -- you are trying to find the number in Z₁₂ that is the (multiplicative) inverse of 5. IOW, the number x such that 5x ≡ 1 (mod 12).

Second, you mentioned something about "if x = 65" -- 65 is not in Z₁₂. This set of numbers contains equivalence classes for 0 through 11.

 

[Mark44]

By the way, your title is misleading. The ring <Z₁₂, +, ##\cdot##> is not a Boolean ring. See https://en.wikipedia.org/wiki/Boolean_ring.

 

[Rectifier]

Thank you for your comment. I will try digest the contents of it later this day.

Hmm, sorry for posting a misleading title, I didnt do it on purpose. Thought that they talked about boolean rings in the problem sinte the chapter in my book is abiut boolean operators, rings, groups and fields.

 

[fresh_42]

Thank you for your reply but unfortunately it didnt make my life easier.I should have specified that in the question above but I am supposed to solve it using gcd and Euclids identity.

You want to solve an equation ##5n + 12m = 1## with any ##m## and the solution ##n##.
You should use the Euclidean algorithm here. (The Euclidean identity is something else, AFAIK.)
##1 = (13-12) = (2\,\cdot\,5 + \underline{3})-12##
##\underline{3} = (15-12)= (3\,\cdot\,5+\underline{0})-12## and thus
##1= ((2+3)\,\cdot\,5) - 2\,\cdot\,12 \equiv 5\,\cdot\,5 \; (12)##.

 

[thelema418]

Understanding gcd(n, 12) = 1, might help you limit which numbers are possible solutions. Understanding properties of addition and multiplication in modulo n can provide some tricks to finding the inverse. With the extended Euclidean strategy, (provided gcd is 1) you can set up

##12 = 1 \cdot 12 + 0 \cdot 5##
##5 = 0 \cdot 12 + 1 \cdot 5##

You would then try to do row manipulations so that you have ## -1 = n \cdot 12 + m \cdot 5##. You then have to find the additive inverse, since there are no negative numbers in the integer ring.

 

[Mark44]

You would then try to do row manipulations so that you have −1=n⋅12+m⋅5. You then have to find the additive inverse, since there are no negative numbers in the integer ring.

The OP didn't explicitly say so, but I have assumed that by 5^-1 he meant the multiplicative inverse.

 

[thelema418]

The OP didn't explicitly say so, but I have assumed that by 5^-1 he meant the multiplicative inverse.

The OP means the multiplicative inverse. The strategy I am explaining yields -m = 1/5. So you have to find the additive inverse at that point to find the multiplicative inverse solution.

EDIT: Since everyone is giving the OP the solution to the problem. The solution process ends with -7 = 1/5. 7 is the additive inverse of 5, so 5 is the solution.

 

[rcgldr]

5^-1 mod 12 is the multiplicative inverse of 5 mod 12. I'm wondering if the extended Euclid algorithm was supposed to be used here.

http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

Since the answer was already given, including a Euclid like series of steps, this is what the extended Euclid algorithm would produce:

   i     q      r    s     t
-------------------------------
|  0  |     |  12 |  1  |  0  |
|  1  |     |   5 |  0  |  1  |
|  2  |  2  |   2 |  1  | -2  |
|  3  |  2  |   1 | -2  |  5  |
|  4  |  2  |   0 |     |     |

(12 x -2) + (5 x 5) = 1

inverse of 5 mod 12 = 5

Note s[ ... ] is not needed, so the algorithm can just work with q[], r[] and t[].

 

[Rectifier]

Thank you all for your replies. Let's say that we then find this multiplicative inverse to 5 which is x then. What if I were to construct my own problem and ask for the number 5 which we know is the inverse of x. Would I then ask for "find multiplicative inverse to ##x##" or "find multiplicative inverse to ##x^{-1}##" or something else?

I hope that I am not asking too many dumb questions here. :s

 

[thelema418]

Thank you all for your replies. Let's say that we then find this multiplicative inverse to 5 which is x then. What if I were to construct my own problem and ask for the number 5 which we know is the inverse of x. Would I then ask for "find multiplicative inverse to ##x##" or "find multiplicative inverse to ##x^{-1}##" or something else?

I hope that I am not asking too many dumb questions here. :s

In English, I believe we more often use the preposition "of." E.g. "Find the multiplicative inverse of to ##x##."

##x^{-1}## represents the multiplicative inverse of ##x##. The phrase ""Find the multiplicative inverse of ##x##" tells us to find ##x^{-1}## . On the other hand, "Find the multiplicative inverse of ##x^{-1}##" tells us to find ##(x^{-1})^{-1}##. As part of your course work, you may be required to prove that ##(x^{-1})^{-1} = x##.