(New page: == Euler <math>\varphi</math>-function == Def: For d <math>\in \mathbb{N}</math> let <math>\varphi(d)</math>=# (i with 0 ≤ i ≤ d-1, gcd(i,d) =1). We used the example in class: -------...) |
|||
| (3 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
== Euler <math>\varphi</math>-function == | == Euler <math>\varphi</math>-function == | ||
Def: For d <math>\in \mathbb{N}</math> let <math>\varphi(d)</math>=# (i with 0 ≤ i ≤ d-1, gcd(i,d) =1). | Def: For d <math>\in \mathbb{N}</math> let <math>\varphi(d)</math>=# (i with 0 ≤ i ≤ d-1, gcd(i,d) =1). | ||
| − | |||
| − | |||
----------------------------- | ----------------------------- | ||
| + | We used the example in class: <br> | ||
<math>(\mathbb{Z}/6\mathbb{Z},+)</math>. Consider a=1. ord(a)=6. | <math>(\mathbb{Z}/6\mathbb{Z},+)</math>. Consider a=1. ord(a)=6. | ||
| Line 24: | Line 23: | ||
I don't understand how we found the <math>\varphi(d)</math> | I don't understand how we found the <math>\varphi(d)</math> | ||
-Jesse | -Jesse | ||
| + | |||
| + | |||
| + | |||
| + | In the table above, there are 6 subgroups. For <math>\varphi(1)</math>, find out how many subgroups there are with only one element. You see that there is only one and that is why <math>\varphi(1)</math> = 1. Then, you look at how many have 2 elements and there is only one. So <math>\varphi(2)</math> = 1. Now look at how many have 3 elements. There is the subgroup {2,4,0} and {4,2,0}. Therefore, <math>\varphi(3)</math> = 2. Finally, <math>\varphi(6)</math> = 2 since there are two subgroups with 6 elements. | ||
| + | |||
| + | Basically, to find <math>\varphi(d)</math>, you look at how many subgroups have d number of elements and the answer to <math>\varphi(d)</math> is the number of these subgroups. | ||
| + | |||
| + | I hope this helps. | ||
| + | |||
| + | -Ozgur | ||
| + | |||
| + | |||
| + | |||
| + | I am having more problems with actually generating the subgroups. Is the subgroup the elements of the main group that divides the generator? That would make sense except for 5 and that's where I am thinking I am wrong...any ideas? | ||
| + | -Neely | ||
| + | |||
| + | |||
| + | |||
| + | Generators in this case are 0,1,2,3,4, and 5. <math>(\mathbb{Z}/6\mathbb{Z},+)</math> is the group. The subgroup generated by the generators should follow the rules of the group. The group uses addition. So for the first generator, 1, we create a subgroup using addition. It gives us {1,2,3,4,5,0}. Now, we use addition for the second generator, which is 2. We add 2 to 2, and we get 4. We add 2 to 4 and we get 0. So the subgroup is {2,4,0}. Now, do this for 3. We get {3,0}. Repeat this process for all the generators. So basically, we use the operation of the group with each generator and we get the subgroups which are created by only using that specific generator. | ||
| + | |||
| + | -Ozgur | ||
Latest revision as of 08:44, 21 September 2008
Euler $ \varphi $-function
Def: For d $ \in \mathbb{N} $ let $ \varphi(d) $=# (i with 0 ≤ i ≤ d-1, gcd(i,d) =1).
We used the example in class:
$ (\mathbb{Z}/6\mathbb{Z},+) $. Consider a=1. ord(a)=6.
Generator | Subgroup Generated | Size of Subgroup
1 | 1,2,3,4,5,0 | 6 = 6/gcd(6,1)
2 | 2,4,0 | 3 = 6/gcd(6,2)
3 | 3,0 | 2 = 6/gcd(6,3)
4 | 4,2,0 | 3 = 6/gcd(6,4)
5 | 5,4,3,2,1,0 | 6 = 6/gcd(6,5)
0 | 0 | 1 = 6/gcd(6,0)
From the example, we found:
$ \varphi(1) $ = 1
$ \varphi(2) $ = 1
$ \varphi(3) $ = 2
$ \varphi(6) $ = 2
I don't understand how we found the $ \varphi(d) $ -Jesse
In the table above, there are 6 subgroups. For $ \varphi(1) $, find out how many subgroups there are with only one element. You see that there is only one and that is why $ \varphi(1) $ = 1. Then, you look at how many have 2 elements and there is only one. So $ \varphi(2) $ = 1. Now look at how many have 3 elements. There is the subgroup {2,4,0} and {4,2,0}. Therefore, $ \varphi(3) $ = 2. Finally, $ \varphi(6) $ = 2 since there are two subgroups with 6 elements.
Basically, to find $ \varphi(d) $, you look at how many subgroups have d number of elements and the answer to $ \varphi(d) $ is the number of these subgroups.
I hope this helps.
-Ozgur
I am having more problems with actually generating the subgroups. Is the subgroup the elements of the main group that divides the generator? That would make sense except for 5 and that's where I am thinking I am wrong...any ideas? -Neely
Generators in this case are 0,1,2,3,4, and 5. $ (\mathbb{Z}/6\mathbb{Z},+) $ is the group. The subgroup generated by the generators should follow the rules of the group. The group uses addition. So for the first generator, 1, we create a subgroup using addition. It gives us {1,2,3,4,5,0}. Now, we use addition for the second generator, which is 2. We add 2 to 2, and we get 4. We add 2 to 4 and we get 0. So the subgroup is {2,4,0}. Now, do this for 3. We get {3,0}. Repeat this process for all the generators. So basically, we use the operation of the group with each generator and we get the subgroups which are created by only using that specific generator.
-Ozgur
