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$.