hi, can anybody prove that?:

Let finite set.

Prove that

( is the euler function)

Thanks

Printable View

- Jan 22nd 2009, 03:21 AMasub1Again, phi euler function
hi, can anybody prove that?:

Let finite set.

Prove that

( is the euler function)

Thanks - Jan 22nd 2009, 08:52 AMThePerfectHacker
- Jan 22nd 2009, 10:29 AMasub1Quote:

Maybe you mean to say ...

And " " i mean to say #A (the cardinal).

Thanks - Jan 22nd 2009, 11:35 AMThePerfectHacker
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 .