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
