Euler totient function

The Euler totient function is defined such that and is the number of positive integers less than or equal to relatively prime with ¹, called the totient #m/def/num

	1	2	3	4	5	6	7	8	9	10	11	12
coprimes	1	1	1,2	1,3	1,2,3,4	1,5	1,2,3,4,5,6	1,3,5,7	1,2,4,5,7,8	1,3,7,9	1,2,3,4,5,6,7,8,9,10	1,5,7,11
	1	1	2	2	4	2	6	4	6	4	10	4

Properties

For any prime , .

Proof of 1.

Consider the set of size . The only elements which are not relatively prime to are those which are divisible by , of which there are , proving ^P1.

#state/tidy | #lang/en | #SemBr

2017, Contemporary Abstract Algebra, p. 83 ↩

Euler totient function

Properties

Footnotes