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
