hi, can anybody prove that?:
Let finite set.
Prove that
( is the euler function)
Thanks
We will define a relation on .
For, define iff for some .
If has order then has order if and only if .
We argue that is an equivalence relation. First, it is reflexsive because and so . Second, it is symmetric because if . Now since it means there is so that . Thus, . We see from here that . Third, it is transitive because if and it means and . Thus, and so .
For define . Because is an equivalence relation it means is a partition of . Let be the number of such partitions, i.e. . We will prove that . We say above, second paragraph that if for to be in i.e. for to have order it is necessary and sufficient for . Therefore, consists of elements of the forms where . We argue that each can be written as were . Now by the division algorithm where . Therefore, . If then and so we have brought to the form . If then . But . Thus, we have brough to the form , the desired form. Finally, if if and only if where . This is because and so which forces . Thus, . Hence, . This means . Therefore, divides .