Euler totient function - Revision history

Vipul: /* Measures of difference */

2026-08-25T19:09:14Z

Measures of difference

← Older revision		Revision as of 19:09, 25 August 2026
Line 69:		Line 69:
	\| <math>\frac{\varphi(n)}{n}</math> \|\| 1 \|\| At each prime <math>p</math>, value is <math>1 - (1/p)</math>. Limit is 1 as <math>p \to \infty</math> \|\| 0 \|\| Consider the sequence of primorials. The corresponding values of <math>\varphi(n)/n</math> are products of the values <math>1 - (1/p)</math> for the first few primes <math>p</math>. The limit of these is the infinite product <math>\prod_p \left(1 - \frac{1}{p}\right)</math> over all prime <math>p</math>. This goes to zero because the infinite sum of the reciprocals of the primes diverges.		\| <math>\frac{\varphi(n)}{n}</math> \|\| 1 \|\| At each prime <math>p</math>, value is <math>1 - (1/p)</math>. Limit is 1 as <math>p \to \infty</math> \|\| 0 \|\| Consider the sequence of primorials. The corresponding values of <math>\varphi(n)/n</math> are products of the values <math>1 - (1/p)</math> for the first few primes <math>p</math>. The limit of these is the infinite product <math>\prod_p \left(1 - \frac{1}{p}\right)</math> over all prime <math>p</math>. This goes to zero because the infinite sum of the reciprocals of the primes diverges.
	\|-		\|-
	\| <math>\frac{\ln \varphi(n)}{\ln n}</math> \|\| 1 \|\| For each prime <math>p</math>, the expression being limited is <math>\ln(p - 1)/\ln p</math> ,which approaches 1. \|\| 1 \|\| We can show that for every <math>\varepsilon > 0</math>, there exists <math>N_\varepsilon</math> such that <math>\varphi(n) \ge n^{1 - \varepsilon}</math> for all <math>n \ge N_\varepsilon</math>.		\| <math>\frac{\ln \varphi(n)}{\ln n}</math> \|\| 1 \|\| For each prime <math>p</math>, the expression being limited is <math>\ln(p - 1)/\ln p</math>, which approaches 1. \|\| 1 \|\| We can show that for every <math>\varepsilon > 0</math>, there exists <math>N_\varepsilon</math> such that <math>\varphi(n) \ge n^{1 - \varepsilon}</math> for all <math>n \ge N_\varepsilon</math>.
	\|}		\|}

Vipul: /* Measures of difference */

2026-08-25T19:08:56Z

Measures of difference

← Older revision		Revision as of 19:08, 25 August 2026
Line 69:		Line 69:
	\| <math>\frac{\varphi(n)}{n}</math> \|\| 1 \|\| At each prime <math>p</math>, value is <math>1 - (1/p)</math>. Limit is 1 as <math>p \to \infty</math> \|\| 0 \|\| Consider the sequence of primorials. The corresponding values of <math>\varphi(n)/n</math> are products of the values <math>1 - (1/p)</math> for the first few primes <math>p</math>. The limit of these is the infinite product <math>\prod_p \left(1 - \frac{1}{p}\right)</math> over all prime <math>p</math>. This goes to zero because the infinite sum of the reciprocals of the primes diverges.		\| <math>\frac{\varphi(n)}{n}</math> \|\| 1 \|\| At each prime <math>p</math>, value is <math>1 - (1/p)</math>. Limit is 1 as <math>p \to \infty</math> \|\| 0 \|\| Consider the sequence of primorials. The corresponding values of <math>\varphi(n)/n</math> are products of the values <math>1 - (1/p)</math> for the first few primes <math>p</math>. The limit of these is the infinite product <math>\prod_p \left(1 - \frac{1}{p}\right)</math> over all prime <math>p</math>. This goes to zero because the infinite sum of the reciprocals of the primes diverges.
	\|-		\|-
	\| <math>\frac{\ln \varphi(n)}{\ln n}</math> \|\| 1 \|\| For each prime <math>p</math>, the ~~limit~~ is <math>\ln(p - 1)/\ln p</math> ,which approaches 1. \|\| 1 \|\| We can show that for every <math>\varepsilon > 0</math>, there exists <math>N_\varepsilon</math> such that <math>\varphi(n) \ge n^{1 - \varepsilon}</math> for all <math>n \ge N_\varepsilon</math>.		\| <math>\frac{\ln \varphi(n)}{\ln n}</math> \|\| 1 \|\| For each prime <math>p</math>, the expression being limited is <math>\ln(p - 1)/\ln p</math> ,which approaches 1. \|\| 1 \|\| We can show that for every <math>\varepsilon > 0</math>, there exists <math>N_\varepsilon</math> such that <math>\varphi(n) \ge n^{1 - \varepsilon}</math> for all <math>n \ge N_\varepsilon</math>.
	\|}		\|}

Vipul: /* Inequalities */

2026-08-25T19:08:02Z

Inequalities

← Older revision		Revision as of 19:08, 25 August 2026
Line 53:		Line 53:
	! Nature of bound (upper bound or lower) !! Formula !! Arithmetic functions used !! Explanation !! Asymptotic implication		! Nature of bound (upper bound or lower) !! Formula !! Arithmetic functions used !! Explanation !! Asymptotic implication
	\|-		\|-
	\| lower \|\| <math>\pi(n) - \omega(n)</math>\|\| <math>\pi(n)</math> is the [[prime-counting function]], and counts the number of primes less than or equal to <math>n</math>, while <math>\omega(n)</math> is the [[prime divisor count function]] of <math>n</math>. \|\| Any prime less than or equal to <math>n</math> that does ''not'' divide <math>n</math> must be relatively prime to <math>n</math>. \|\| <math>\pi(n) \sim \operatorname{Li}(n)</math> (which grows approximately as <math>n / \~~log~~ n</math>), whereas <math>\omega(n) = O(\~~log~~ n)</math>. Thus, we get an asymptotic lower bound of <math>~\operatorname{Li}(n)</math>. Note that this estimation relies on the [[prime number theorem]].		\| lower \|\| <math>\pi(n) - \omega(n)</math>\|\| <math>\pi(n)</math> is the [[prime-counting function]], and counts the number of primes less than or equal to <math>n</math>, while <math>\omega(n)</math> is the [[prime divisor count function]] of <math>n</math>. \|\| Any prime less than or equal to <math>n</math> that does ''not'' divide <math>n</math> must be relatively prime to <math>n</math>. \|\| <math>\pi(n) \sim \operatorname{Li}(n)</math> (which grows approximately as <math>n / \ln n</math>), whereas <math>\omega(n) = O(\ln n)</math>. Thus, we get an asymptotic lower bound of <math>~\operatorname{Li}(n)</math>. Note that this estimation relies on the [[prime number theorem]].
	\|-		\|-
	\| upper \|\| <math>n - \sigma_0(n) + 1</math> \|\| <math>\sigma_0(n)</math> is the [[divisor count function]], counting the total number of divisors of <math>n</math> \|\| With the exception of 1, any number in <math>\{1, 2, \dots, n\}</math> cannot be both a divisor of <math>n</math> and relatively prime to <math>n</math>. \|\| Nothing specifically, but it does show that for non-primes, there is a relatively sharp demarcation between <math>n</math> and <math>\varphi(n)</math> (in terms of differences, not ratios).		\| upper \|\| <math>n - \sigma_0(n) + 1</math> \|\| <math>\sigma_0(n)</math> is the [[divisor count function]], counting the total number of divisors of <math>n</math> \|\| With the exception of 1, any number in <math>\{1, 2, \dots, n\}</math> cannot be both a divisor of <math>n</math> and relatively prime to <math>n</math>. \|\| Nothing specifically, but it does show that for non-primes, there is a relatively sharp demarcation between <math>n</math> and <math>\varphi(n)</math> (in terms of differences, not ratios).

Vipul: /* Properties */

2026-08-25T18:42:28Z

Properties

← Older revision		Revision as of 18:42, 25 August 2026
Line 31:		Line 31:
	\| [[dissatisfies property::completely multiplicative function]] \|\| No \|\| It is not true for arbitrary natural numbers <math>m</math> and <math>n</math> that <math>\varphi(mn) = \varphi(m)\varphi(n)</math>. For instance, if <math>m = n = 2</math>, then <math>\varphi(m) = \varphi(n) = 1</math> whereas <math>\varphi(mn)</math> is 2.		\| [[dissatisfies property::completely multiplicative function]] \|\| No \|\| It is not true for arbitrary natural numbers <math>m</math> and <math>n</math> that <math>\varphi(mn) = \varphi(m)\varphi(n)</math>. For instance, if <math>m = n = 2</math>, then <math>\varphi(m) = \varphi(n) = 1</math> whereas <math>\varphi(mn)</math> is 2.
	\|-		\|-
	\| [[satisfies property::divisibility-preserving function]] \|\| Yes \|\| If <math>m</math> and <math>n</math> are natural numbers such that <math>m</math>divides <math>n</math>, then <math>\varphi(m)</math> divides <math>\varphi(n)</math>.		\| [[satisfies property::divisibility-preserving function]] \|\| Yes \|\| If <math>m</math> and <math>n</math> are natural numbers such that <math>m</math> divides <math>n</math>, then <math>\varphi(m)</math> divides <math>\varphi(n)</math>.
	\|}		\|}

Vipul at 18:41, 25 August 2026

2026-08-25T18:41:12Z

@@ Line 47: / Line 47: @@
 * '''Primes are high points''': We also have <math>\varphi(n) \le n - 1</math> for <matH>n > 1</math>. Equality occurs if and only if <math>n</math> is a [[prime number]].
 * '''Primorials are low points''': Roughly, the numbers occurring as [[primorial]]s (products of the first few primes) have the lowest value of <math>\varphi(n)</math> relative to <math>n</math>, compared with other similarly sized numbers.
 ===Measures of difference===
@@ Line 131: / Line 141: @@
 | <math>\sigma_1</math> || <math>E</math> || <math>\sigma_1</math> || no name || no name
 |}
 ==Relation with properties of numbers==
@@ Line 147: / Line 147: @@
 * [[Prime number]]: A natural number <math>n</math> such that <math>\varphi(n) = n-1</math>.
 * [[Polygonal number]]: A natural number <math>n</math> such that <math>\varphi(n)</math> is a power of <math>2</math>, or equivalently, such that the regular <math>n</math>-gon is constructible using straightedge and compass.
 ==Dirichlet series==

Vipul: /* Measures of difference */

2026-08-25T18:39:37Z

Measures of difference

← Older revision		Revision as of 18:39, 25 August 2026
Line 57:		Line 57:
	\| <math>\varphi(n) - n</math> \|\| -1 \|\| maximum value of -1 occurs at primes \|\| <math>-\infty</math> \|\| Consider the sequence of powers 2. <math>\varphi(2^k) = 2^{k-1}</math>, so <math>\varphi(2^k) - 2^k = -2^{k-1} \to -\infty</math>.		\| <math>\varphi(n) - n</math> \|\| -1 \|\| maximum value of -1 occurs at primes \|\| <math>-\infty</math> \|\| Consider the sequence of powers 2. <math>\varphi(2^k) = 2^{k-1}</math>, so <math>\varphi(2^k) - 2^k = -2^{k-1} \to -\infty</math>.
	\|-		\|-
	\| <math>\frac{\varphi(n)}{n}</math> \|\| 1 \|\| At each prime <math>p</math>, value is <math>1 - (1/p)</math>. Limit is 1 as <math>p \to \infty</math> \|\| 0 \|\| Consider the sequence of primorials. The corresponding values of <math>\varphi(n)/n</math> are products of the values <math>1 - (1/p)</math> for the first few primes <math>p</math>. The limit of these is the infinite product <math>\prod_p \left(1 - \frac{1}{p}\right)</math> over all prime <math>p</math>. This ~~diverges~~ because the infinite sum of the reciprocals of the primes diverges.		\| <math>\frac{\varphi(n)}{n}</math> \|\| 1 \|\| At each prime <math>p</math>, value is <math>1 - (1/p)</math>. Limit is 1 as <math>p \to \infty</math> \|\| 0 \|\| Consider the sequence of primorials. The corresponding values of <math>\varphi(n)/n</math> are products of the values <math>1 - (1/p)</math> for the first few primes <math>p</math>. The limit of these is the infinite product <math>\prod_p \left(1 - \frac{1}{p}\right)</math> over all prime <math>p</math>. This goes to zero because the infinite sum of the reciprocals of the primes diverges.
	\|-		\|-
	\| <math>\frac{\ln \varphi(n)}{\ln n}</math> \|\| 1 \|\| For each prime <math>p</math>, the limit is <math>\ln(p - 1)/\ln p</math> ,which approaches 1. \|\| 1 \|\| We can show that for every <math>\varepsilon > 0</math>, there exists <math>N_\varepsilon</math> such that <math>\varphi(n) \ge n^{1 - \varepsilon}</math> for all <math>n \ge N_\varepsilon</math>.		\| <math>\frac{\ln \varphi(n)}{\ln n}</math> \|\| 1 \|\| For each prime <math>p</math>, the limit is <math>\ln(p - 1)/\ln p</math> ,which approaches 1. \|\| 1 \|\| We can show that for every <math>\varepsilon > 0</math>, there exists <math>N_\varepsilon</math> such that <math>\varphi(n) \ge n^{1 - \varepsilon}</math> for all <math>n \ge N_\varepsilon</math>.

Vipul: /* Inequalities */

2026-08-25T18:38:10Z

Inequalities

← Older revision		Revision as of 18:38, 25 August 2026
Line 138:		Line 138:
	! Nature of bound (upper bound or lower) !! Formula !! Arithmetic functions used !! Explanation !! Asymptotic implication		! Nature of bound (upper bound or lower) !! Formula !! Arithmetic functions used !! Explanation !! Asymptotic implication
	\|-		\|-
	\| lower \|\| <math>\pi(n) - \omega(n)</math>\|\| <math>\pi(n)</math> is the [[prime-counting function]], and counts the number of primes less than or equal to <math>n</math>, while <math>\omega(n)</math> is the [[prime divisor count function]] of <math>n</math>. \|\| Any prime less than or equal to <math>n</math> that does ''not'' divide <math>n</math> must be relatively prime to <math>n</math>. \|\| <math>\pi(n) \sim \operatorname{Li}(n)</math>, whereas <math>\omega(n) = O(\log n)</math>. Thus, we get an asymptotic lower bound of <math>~\operatorname{Li}(n)</math>. Note that this estimation relies on the [[prime number theorem]].		\| lower \|\| <math>\pi(n) - \omega(n)</math>\|\| <math>\pi(n)</math> is the [[prime-counting function]], and counts the number of primes less than or equal to <math>n</math>, while <math>\omega(n)</math> is the [[prime divisor count function]] of <math>n</math>. \|\| Any prime less than or equal to <math>n</math> that does ''not'' divide <math>n</math> must be relatively prime to <math>n</math>. \|\| <math>\pi(n) \sim \operatorname{Li}(n)</math> (which grows approximately as <math>n / \log n</math>), whereas <math>\omega(n) = O(\log n)</math>. Thus, we get an asymptotic lower bound of <math>~\operatorname{Li}(n)</math>. Note that this estimation relies on the [[prime number theorem]].
	\|-		\|-
	\| upper \|\| <math>n - \sigma_0(n) + 1</math> \|\| <math>\sigma_0(n)</math> is the [[divisor count function]], counting the total number of divisors of <math>n</math> \|\| With the exception of 1, any number in <math>\{1, 2, \dots, n\}</math> cannot be both a divisor of <math>n</math> and relatively prime to <math>n</math>. \|\| Nothing specifically, but it does show that for non-primes, there is a relatively sharp demarcation between <math>n</math> and <math>\varphi(n)</math> (in terms of differences, not ratios).		\| upper \|\| <math>n - \sigma_0(n) + 1</math> \|\| <math>\sigma_0(n)</math> is the [[divisor count function]], counting the total number of divisors of <math>n</math> \|\| With the exception of 1, any number in <math>\{1, 2, \dots, n\}</math> cannot be both a divisor of <math>n</math> and relatively prime to <math>n</math>. \|\| Nothing specifically, but it does show that for non-primes, there is a relatively sharp demarcation between <math>n</math> and <math>\varphi(n)</math> (in terms of differences, not ratios).

Vipul: /* Inequalities */

2026-08-25T18:37:25Z

Inequalities

← Older revision		Revision as of 18:37, 25 August 2026
Line 138:		Line 138:
	! Nature of bound (upper bound or lower) !! Formula !! Arithmetic functions used !! Explanation !! Asymptotic implication		! Nature of bound (upper bound or lower) !! Formula !! Arithmetic functions used !! Explanation !! Asymptotic implication
	\|-		\|-
	\| lower \|\| <math>\pi(n) - \omega(n)</math>\|\| <math>\pi(n)</math> is the [[prime-counting function]], and counts the number of primes less than or equal to <math>n</math>, while <math>\omega(n)</math> is the [[prime divisor count function]] of <math>n</math>. \|\| Any prime less than or equal to <math>n</math> that does ''not'' divide <math>n</math> must be relatively prime to <math>n</math>. \|\| <math>\pi(n) \sim ~~\frac{n}{~~\operatorname{Li}(n)}</math>, whereas <math>\omega(n) = O(\log n)</math>. Thus, we get an asymptotic lower bound of <math>~n/\operatorname{Li}(n)</math>. Note that this estimation relies on the [[prime number theorem]].		\| lower \|\| <math>\pi(n) - \omega(n)</math>\|\| <math>\pi(n)</math> is the [[prime-counting function]], and counts the number of primes less than or equal to <math>n</math>, while <math>\omega(n)</math> is the [[prime divisor count function]] of <math>n</math>. \|\| Any prime less than or equal to <math>n</math> that does ''not'' divide <math>n</math> must be relatively prime to <math>n</math>. \|\| <math>\pi(n) \sim \operatorname{Li}(n)</math>, whereas <math>\omega(n) = O(\log n)</math>. Thus, we get an asymptotic lower bound of <math>~\operatorname{Li}(n)</math>. Note that this estimation relies on the [[prime number theorem]].
	\|-		\|-
	\| upper \|\| <math>n - \sigma_0(n) + 1</math> \|\| <math>\sigma_0(n)</math> is the [[divisor count function]], counting the total number of divisors of <math>n</math> \|\| With the exception of 1, any number in <math>\{1, 2, \dots, n\}</math> cannot be both a divisor of <math>n</math> and relatively prime to <math>n</math>. \|\| Nothing specifically, but it does show that for non-primes, there is a relatively sharp demarcation between <math>n</math> and <math>\varphi(n)</math> (in terms of differences, not ratios).		\| upper \|\| <math>n - \sigma_0(n) + 1</math> \|\| <math>\sigma_0(n)</math> is the [[divisor count function]], counting the total number of divisors of <math>n</math> \|\| With the exception of 1, any number in <math>\{1, 2, \dots, n\}</math> cannot be both a divisor of <math>n</math> and relatively prime to <math>n</math>. \|\| Nothing specifically, but it does show that for non-primes, there is a relatively sharp demarcation between <math>n</math> and <math>\varphi(n)</math> (in terms of differences, not ratios).

Vipul: /* Algebraic significance */

2026-08-25T18:32:45Z

Algebraic significance

← Older revision		Revision as of 18:32, 25 August 2026
Line 36:		Line 36:
	===Algebraic significance===		===Algebraic significance===

	The Euler ~~phi-~~function of <math>n</math> is important in the following ways:		The Euler totient function of <math>n</math> is important in the following ways:

	* It is the number of generators of the cyclic group of order <math>n</math>.		* It is the number of generators of the cyclic group of order <math>n</math>.

Vipul: /* Initial values */

2014-01-29T22:44:31Z

Initial values

← Older revision		Revision as of 22:44, 29 January 2014
Line 65:		Line 65:

	{\| class="sortable" border="1"		{\| class="sortable" border="1"
	! <math>n</math> !! Prime factorization !! Totient function <math>\varphi(n)</math> !! <math>n - \varphi(n)</math> (equals 1 iff <math>n</math> is prime) !! <math>\varphi(n)/n</math> (reduced, equals product of <math>(1 - 1/p)</math> for primes <math>p</math> dividing <math>n</math> -- depends only on the ''set'' of prime divisors) !! Universal exponent <math>\lambda(n)</math> !! <math>\varphi(n)/\lambda(n)		! <math>n</math> !! Prime factorization !! Totient function <math>\varphi(n)</math> !! <math>n - \varphi(n)</math> (equals 1 iff <math>n</math> is prime) !! <math>\varphi(n)/n</math> (reduced, equals product of <math>(1 - 1/p)</math> for primes <math>p</math> dividing <math>n</math> -- depends only on the ''set'' of prime divisors) !! Universal exponent <math>\lambda(n)</math> !! <math>\varphi(n)/\lambda(n)</math>
	\|-		\|-
	\| [[1]] \|\| empty \|\| 1 \|\| 0 \|\| 1 \|\| 1 \|\| 1		\| [[1]] \|\| empty \|\| 1 \|\| 0 \|\| 1 \|\| 1 \|\| 1
Line 91:		Line 91:
	\| Power <math>p^k</math>, <math>p</math> odd \|\| <math>p^k</math> \|\| <math>p^{k-1}(p-1)</math> \|\| <math>p^{k-1}</math> \|\| <math>1 - (1/p)</math> \|\| <math>p^{k-1}</math> \|\| 1		\| Power <math>p^k</math>, <math>p</math> odd \|\| <math>p^k</math> \|\| <math>p^{k-1}(p-1)</math> \|\| <math>p^{k-1}</math> \|\| <math>1 - (1/p)</math> \|\| <math>p^{k-1}</math> \|\| 1
	\|}		\|}

	==Related arithmetic functions==		==Related arithmetic functions==