Boolean rings - residues

Tags:
1. Sep 12, 2016

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.

2. Sep 12, 2016

Staff: Mentor

No, I don't think so. Above, you have "Find 5-1"
Presumably this means that you want to find a number x in Z12 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.

3. Sep 12, 2016

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.

4. Sep 12, 2016

Staff: Mentor

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 Z12 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 Z12 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 Z12. This set of numbers contains equivalence classes for 0 through 11.

5. Sep 12, 2016

Staff: Mentor

6. Sep 12, 2016

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.

7. Sep 12, 2016

Staff: Mentor

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

8. Sep 12, 2016

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.

9. Sep 12, 2016

Staff: Mentor

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

10. Sep 12, 2016

thelema418

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.

Last edited: Sep 12, 2016
11. Sep 12, 2016

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:

Code (Text):

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[].

Last edited: Sep 13, 2016
12. Sep 13, 2016

Rectifier

Thank you all for your replies. Lets 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

13. Sep 13, 2016

thelema418

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