# Group Theory

Printable View

• Oct 10th 2012, 04:22 AM
weijing85
Group Theory
Hi anyone knows how to solve this?

i) Consider Z*15, the group of invertible element of Z15 under the operation of multiplication (mod 15). What is the size of Z*15?
ii) Consider Z*6, the group of invertible element of Z6 under the operation of multiplication (mod 6). What is the size of Z*6?

Appreciate if anyone can help me (:
• Oct 10th 2012, 04:46 AM
emakarov
Re: Group Theory
Recall that the multiplicative inverse modulo n is found using the Bézout's identity. Also recall that the number of positive integers less than or equal to n that are relatively prime to n is given by the Euler's totient function.

For more, see Multiplicative group of integers modulo n.
• Oct 10th 2012, 06:03 AM
johnsomeone
Re: Group Theory
The key thing to remember is that "\$\displaystyle x\$ has multiplicative inverse in \$\displaystyle \mathbb{Z}_n^*\$ if and only if \$\displaystyle x\$ and \$\displaystyle n\$ are relatively prime."
(One way is straightforward to prove, the other way is from Bezout's identity.)

The details are found in emakarov's post and its links.
• Oct 14th 2012, 07:08 AM
weijing85
Re: Group Theory
Guys, i still dun get it :( after reading the links :( will it be possible if u can enlighten me :)
• Oct 14th 2012, 09:13 AM
johnsomeone
Re: Group Theory
Do you know what the definition is of an invertible element in \$\displaystyle \mathbb{Z}_n\$? If yes, then try to apply it, one element at a time, to \$\displaystyle \mathbb{Z}_{15}\$. In other words, go through the non-zero elements of \$\displaystyle \mathbb{Z}_{15}\$, and for each, either find the inverse, or declare that it's not invertible. Then count the number of elements that have an inverse.

I'll do \$\displaystyle \mathbb{Z}_{6}\$ for you:

In \$\displaystyle \mathbb{Z}_{6}\$, [1] [1] = [1], so [1] is invertible, and its inverse is [1].

In \$\displaystyle \mathbb{Z}_{6}\$, [2] [3] = [0], so [2] is not invertible (if [2] [a] = [1], then [2] [a] [3]= [1] [3] = [3], so [0] = [3]. Impossible.)

In \$\displaystyle \mathbb{Z}_{6}\$, [3] [2] = [0], so [3] is not invertible (same reasoning as with [2].)

In \$\displaystyle \mathbb{Z}_{6}\$, [4] [3] = [12] = [0], so [4] is not invertible (same reasoning as with [2].)

In \$\displaystyle \mathbb{Z}_{6}\$, [5] [5] = [25] = [24+1] = [(6)(4)+1] = [1], so [5] is invertible, with inverse [5].

Thus \$\displaystyle \mathbb{Z}_{6}^* = \{ [1], [5] \}\$, and so \$\displaystyle |\mathbb{Z}_{6}^*| = 2\$.

Here are a few from \$\displaystyle \mathbb{Z}_{15}\$:

In \$\displaystyle \mathbb{Z}_{15}\$, [1] [1] = [1], so [1] is invertible, and its inverse is [1].

In \$\displaystyle \mathbb{Z}_{15}\$, [2] [8] = [16] = [1], so [2] is invertible, and its inverse is [8].

In \$\displaystyle \mathbb{Z}_{15}\$, [3] [5] = [15] = [0], so [3] is not invertible.

In \$\displaystyle \mathbb{Z}_{15}\$, [4] [4] = [16] = [1], so [4] is invertible, and its inverse is [4].

... (try to fill these in) ...

In \$\displaystyle \mathbb{Z}_{15}\$, [13] [7] = [91] = [(15)(6)+1] = [1], so [13] is invertible, and its inverse is [7].

In \$\displaystyle \mathbb{Z}_{15}\$, [14] [14] = [196] = [195+1] = [(15)(13)+1] = [1], so [14] is invertible, and its inverse is [14].
• Oct 15th 2012, 09:44 PM
weijing85
Re: Group Theory
Thanks! I worked out.
I got |Z*15| = {[1],[2],[4],[7],[8],[13],[14]}

(:
• Oct 15th 2012, 10:01 PM
weijing85
Re: Group Theory
Miss out 11.
I got |Z*15| = {[1],[2],[4],[7],[8],[11],[13],[14]}

Thanks you very much!
• Oct 16th 2012, 01:41 PM
johnsomeone
Re: Group Theory
If the problem makes sense to you now, you might want to go back and reread emakarov's post and its links. That now might make more sense.