Euler's totient function: Difference between revisions

Revision as of 17:40, 19 June 2006

Euler's totient function, $\phi(n)$ , determines the number of integers less than a given positive integer that is relatively prime to that integer.

Formulas

Given the prime factorization of ${n} = {p}_1^{e_1}{p}_2^{e_2} \cdots {p}_n^{e_n}$ , then one formula for $\phi(n)$ is $\phi(n) = n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right) \cdots \left(1-\frac{1}{p_n}\right)$ .

Identities

For prime p, $\phi(p)=p-1$ , because all numbers less than ${p}$ are relatively prime to it.

For relatively prime ${a}, {b}$ , $\phi{(a)}\phi{(b)} = \phi{(ab)}$ .

In fact, we also have ${a}, {b}$ , we have $\phi{(a)}\phi{(b)}\gcd(a,b)=\phi{(ab)}\phi({\gcd(a,b)})$ .

For any $n$ , we have $\sum_{d|n}\phi(d)=n$ where the sum is taken over all divisors d of $n$ .

Revision as of 22:03, 18 June 2006 view source Chess64 (talk \| contribs) 431 edits mNo edit summary ← Older edit		Revision as of 17:40, 19 June 2006 view source Inscrutableroot (talk \| contribs) 307 edits m proofreading Newer edit →
Line 1:		Line 1:
	'''Euler's totient function''', <math>\phi(n)</math>, determines the number of integers less than a given positive integer that ~~are~~ [[relatively prime]] to that integer.		'''Euler's totient function''', <math>\phi(n)</math>, determines the number of integers less than a given positive integer that is [[relatively prime]] to that integer.

	=== Formulas ===		=== Formulas ===

Page

Toolbox

Search

Euler's totient function: Difference between revisions

Revision as of 17:40, 19 June 2006

Formulas

Identities

See also