Number theory MOC

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 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

1. 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.

---

tidy | en | sembr

Footnotes

1. 2017, Contemporary Abstract Algebra, p. 83 ↩