| Line 23: | 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 | ||
Revision as of 11:12, 13 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
